# [Koko Eating Bananas](https://leetcode.com/problems/koko-eating-bananas/)
###### tags: `Leetcode`, `Medium`, `Binary Search`

## Approach

* The number of bananas that can be eaten by Koko is in the range of `1 to max(piles)`. Set `result` to `max(piles)` initially
* Apply binary search to this range and for every `mid` value check the amount of time taken to eat the bananas from the piles
* For this, iterate through every pile and perform ceil division of `pile / mid`. Keep adding the quotient to the sum. If `sum < h` then fewer bananas can be eaten per hour by Koko. Shift `right` pointer to `mid - 1`. `result = min(result, mid)`.
* If `sum > h` then more bananas have to be eaten by Koko. Shift `left` pointer to `mid + 1`.
* Return result

## Asymptotic Analysis
### Time Complexity: **O(N log(M))**
N = `max(piles)`
M = `len(piles)`
### Space Complexity: **O(1)**

## Code

import math
from typing import List


class KokoEatingBananas:
    def min_eating_speed(self, piles: List[int], h: int) -> int:
        left, right = 1, max(piles)
        result = right
        while left <= right:
            mid = (right + left) // 2
            hours = 0
            for pile in piles:
                hours += math.ceil(pile / mid)
            if hours <= h:
                result = min(mid, result)
                right = mid - 1
            else:
                left = mid + 1
        return result


piles1, h1 = [3, 6, 7, 11], 8
print("Koko can eat " + str(KokoEatingBananas().min_eating_speed(piles1, h1)) + " bananas per hour.")