Koko Eating bananas

119.Koko Eating Bananas

Binary Search

Problem Statement:

Given an array piles representing the number of bananas in each pile and an integer H representing the number of hours Koko has to eat all the bananas, find the minimum integer K such that Koko can eat all the bananas within H hours. Koko can decide her speed, eating K bananas per hour, and she must finish eating one pile before moving to the next.

Algorithm:

1. Use binary search to find the smallest K that satisfies the condition of eating all bananas in H hours.
2. Define the search range for K:
   • Lower bound: 1 banana per hour.
   • Upper bound: The size of the largest pile.
3. For each K in the binary search range:
   • Simulate the eating process to calculate the total hours required using a helper function canEatAll.
   • If Koko can finish within H hours, move the upper bound down; otherwise, move the lower bound up.
4. The result is the smallest K that satisfies the condition.

Complexity:

Time: O(n × log(maxPile)), where n is the number of piles, and maxPile is the largest pile size | Space: O(1).

Java Implementation:

public class Solution {
    public int minEatingSpeed(int[] piles, int H) {
        int lo = 1, hi = getMaxPile(piles);

        // Binary search to find the smallest valid K.
        while (lo <= hi) {
            int K = lo + ((hi - lo) >> 1);
            if (canEatAll(piles, K, H)) {
                hi = K - 1;
            } else {
                lo = K + 1;
            }
        }

        return lo;
    }

    private boolean canEatAll(int[] piles, int K, int H) {
        int countHour = 0; // Hours taken to eat all bananas at speed K.

        for (int pile : piles) {
            countHour += pile / K;
            if (pile % K != 0)
                countHour++;
        }
        return countHour <= H;
    }

    private int getMaxPile(int[] piles) {
        int maxPile = Integer.MIN_VALUE;
        for (int pile : piles) {
            maxPile = Math.max(pile, maxPile);
        }
        return maxPile;
    }
}
                

Python Implementation:

def minEatingSpeed(piles, H):
    def can_eat_all(K):
        hours = 0
        for pile in piles:
            hours += (pile + K - 1) // K
        return hours <= H

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if can_eat_all(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo
                

C++ Implementation:

class Solution {
public:
    int minEatingSpeed(vector& piles, int H) {
        int lo = 1, hi = *max_element(piles.begin(), piles.end());

        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (canEatAll(piles, mid, H)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

private:
    bool canEatAll(const vector& piles, int K, int H) {
        int hours = 0;
        for (int pile : piles) {
            hours += (pile + K - 1) / K;
            if (hours > H) return false;
        }
        return true;
    }
};