Koko Eating Bananas

🔗 Leetcode Problem

Koko Eating Bananas is a binary search problem where we help Koko determine how many bananas Koko needs to eat if Koko were to eat the minimum number of bananas in such a way that there are no bananas left after H hours.

Pseudocode

Sort piles and declare result equal to the largest # of bananas. low is 1, high is the largest pile count.

While low is less than or equal to high, find the mid between low and high - mid represents the number of bananas Koko will hypothetically eat.

See if this mid value works by reducing all piles, summing all the total of pile / mid and rounding up. For example, if one pile was 6, and the mid number is 5, Math.ceil(6/5) === 2, because it will take 2 hours for Koko to eat a pile of 6 bananas if Koko were to eat 5 max bananas per hour.

See if mid is less than or equal to h hours. If so, set result to mid, and try for a lower number by setting high = mid - 1

If not, try for a larger number by setting low to mid + 1.

Code

var minEatingSpeed = function(piles, h) {
    piles.sort((a, b) => a - b);

    // at most, Koko needs to eat at least the biggest pile amount.
    let result = piles[piles.length - 1];
    let low = 1;
    let high = piles[piles.length - 1];

    while (low <= high) {
        const mid = Math.floor(low + (high - low) / 2);
        const hoursToEatAllBananas = piles.reduce((acc, pile) => acc += Math.ceil(pile / mid), 0);

        if (hoursToEatAllBananas <= h) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return result;
};