# Koko Eating Bananas (Leetcode #875)

Koko loves to eat bananas. There are `n` piles of bananas, the `i<sup>th</sup>` pile has `piles[i]` bananas. The guards have gone and will come back in `h` hours.

Koko can decide her bananas-per-hour eating speed of `k`. Each hour, she chooses some pile of bananas and eats `k` bananas from that pile. If the pile has less than `k` bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return *the minimum integer*`k`*such that she can eat all the bananas within*`h`*hours*.

**Example 1:**

```python
Input: piles = [3,6,7,11], h = 8
Output: 4
```

**Example 2:**

```python
Input: piles = [30,11,23,4,20], h = 5
Output: 30
```

**Example 3:**

```python
Input: piles = [30,11,23,4,20], h = 6
Output: 23
```

**Constraints:**

* `1 <= piles.length <= 10<sup>4</sup>`
    
* `piles.length <= h <= 10<sup>9</sup>`
    
* `1 <= piles[i] <= 10<sup>9</sup>`
    

### Answer

Let's first break down the question. We need to find the speed at which Koko will eat all the bananas given we have h hours.

We first define a function to calculate how many hours it would take given that Koko eats k bananas per hour.

```python
        def bananas_eaten_per_hour(k):
            total_hours = 0
            for pile in piles:
                total_hours += (pile + k - 1) // k
            return total_hours
```

Now we can use binary search to go through every possible answer to find the solution.

The lower bound of possible answer is k = 1 and the upper bound is k = max(piles)

```python
left, right = 1, max(piles)
```

All that is left now is to use the binary search to find the correct answer

```python
        while left < right:
            mid = (left + right) // 2
            if bananas_eaten_per_hour(mid) <= h:
                right = mid
            else:
                left = mid + 1
                
        return left
```

Note here that the implementation of binary search is a little different than what we expected. Let's go through the code line by line to understand how the binary search works.

1. ```python
     mid = (left + right) // 2
    ```
    
    We find the middle number in order to implement a binary search
    
2. ```python
                 if bananas_eaten_per_hour(mid) <= h:
                     right = mid
    ```
    
    Since we are trying to find the minimum speed the if bananas\_eaten\_per\_hour(mid) &lt;= h is true then Koko can eat all the banans at speed mid, hence we need to consider mid in our next search
    
3. ```python
                 else:
                     left = mid + 1
    ```
    
    If bananas\_eaten\_per\_hour(mid) &gt; h then we won't have to consider mid in the next search, hence left = mid + 1
    

Finally, the convergence point of this loop is when left == right. Hence we can return left for the final answer.

```python
class Solution(object):
    def minEatingSpeed(self, piles, h):
        """
        :type piles: List[int]
        :type h: int
        :rtype: int
        """
        def bananas_eaten_per_hour(k):
            total_hours = 0
            for pile in piles:
                total_hours += (pile + k - 1) // k
            return total_hours
        
        left, right = 1, max(piles)
        
        while left < right:
            mid = (left + right) // 2
            if bananas_eaten_per_hour(mid) <= h:
                right = mid
            else:
                left = mid + 1
                
        return left
```

**Time Complexity**

Since this is binary search the time complexity is O(log n)

**Space Complexity**

O(1)