Koko Eating Bananas medium

Problem Statement

Koko loves to eat bananas. There are piles of bananas, where piles[i] is the number of bananas in the i-th pile. Koko can decide her eating speed k. Each hour, she eats k bananas. If the number of bananas in a pile is less than k, she will take only that number of bananas. Koko likes to eat all the bananas before the hour hand reaches h.

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

Example 1

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

Example 2

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

Steps to Solve

1. Binary Search: The problem can be efficiently solved using binary search. The search space for k (eating speed) is from 1 (minimum speed to eat at least one banana per hour) to the maximum number of bananas in any pile (maximum speed).

2. Check Feasibility: For each potential k, we need to check if Koko can eat all bananas within h hours. This involves iterating through the piles array and calculating the time required to eat each pile. The time taken for a pile is ceil(piles[i] / k). If the total time exceeds h, then k is too small and we need to search in the higher half. Otherwise, k might be a valid solution, and we should search in the lower half to find a smaller k.

3. Return Minimum k: The binary search continues until the left and right pointers converge. The final value of k will be the minimum eating speed that satisfies the condition.

Explanation

The core idea is that we can efficiently check if a given eating speed k is feasible using the ceiling function for division. The binary search allows us to quickly narrow down the search space to find the minimum feasible k. The time complexity is logarithmic due to the binary search.

Code (C++)

#include <vector>
#include <cmath>

using namespace std;

int minEatingSpeed(vector<int>& piles, int h) {
    int left = 1; // Minimum speed
    int right = *max_element(piles.begin(), piles.end()); // Maximum speed

    int result = right; // Initialize result to the maximum speed

    while (left <= right) {
        int mid = left + (right - left) / 2; // Avoid potential integer overflow
        long long totalTime = 0; // Use long long to handle potential large sums

        for (int pile : piles) {
            totalTime += ceil((double)pile / mid);
        }

        if (totalTime <= h) {
            result = mid; // Found a possible solution, try smaller speeds
            right = mid - 1;
        } else {
            left = mid + 1; // Need higher speed
        }
    }

    return result;
}

Complexity

• Time Complexity: O(N log M), where N is the number of piles and M is the maximum number of bananas in a pile. The log M factor comes from the binary search. The loop inside binary search iterates N times in each step.

• Space Complexity: O(1). The algorithm uses a constant amount of extra space.