Koko Eating Bananas

Koko loves to eat bananas. There are $n$ piles of bananas, the $i^{th}$ 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

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

 

Solution Implementation

The Feasibility Check

Implements the predicate.

  bool canFinish(const vector<int> &piles, int h, int k) {
    int hours = 0;

    for (auto p: piles) {
        hours += (p + (k - 1)) / k;
        if (hours > h) return false;
    }

    return true;
}
  
  boolean canFinish(int[] piles, int h, int k) {
    int hours = 0;

    for (int pile : piles) {
        hours += (pile + (k - 1)) / k;
        if (hours > h) return false;
    }

    return true;
}

Explanation:

  • Loops over each pile of bananas $(p)$.
  • Computes $ceil(p / k)$ by $(p + (k – 1)) / k$.
  • Accumulates total $hours$.
  • If at any point $hours > h$, returns $false$ immediately (speed $k$ is too slow).
  • Otherwise, returns $true$ (speed $k$ lets Koko finish in time).

 

Binary-Search on the Answer 

  int minEatingSpeed(vector<int> &piles, int h) {
    int l = 1;
    int r = *max_element(piles.begin(), piles.end());

    while (l < r) {
        int mid = l + (r - l) / 2;
        if (canFinish(piles, h, mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }

    return r;
}
  
  int minEatingSpeed(int[] piles, int h) {
    int l = 1;
    int r = Arrays.stream(piles).max().getAsInt();

    while (l < r) {
        int mid = l + (r - l) / 2;
        if (canFinish(piles, h, mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }

    return r;
}

 

Binary-Search on the Answer (Alternative Approach) 

  int minEatingSpeed(vector<int> &piles, int h) {
    int l = 0;
    int r = *max_element(piles.begin(), piles.end()) + 1;

    while (r - l > 1) {
        int mid = l + (r - l) / 2;
        if (canFinish(piles, h, mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }

    return r;
}
  
  int minEatingSpeed(int[] piles, int h) {
    int l = 0;
    int r = Arrays.stream(piles).max().getAsInt() + 1;

    while (r - l > 1) {
        int mid = l + (r - l) / 2;
        if (canFinish(piles, h, mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }

    return r;
}

Explanation:

  1. Initialization
    • $l = 1$ (minimum possible speed).
    • $r = max(piles)$ (at worst, eat the largest pile in one hour).
  2. Loop Condition
    • While $l < r$, we haven’t narrowed down to a single speed.
  3. Midpoint & Decision
    • $mid = l + (r–l)/2$ picks the candidate speed.
    • Call $canFinish(piles, h, mid)$:
    • $true \to$ Koko can finish at speed $mid$, so the optimal speed is $\leq mid$. We set $r = mid$.
    • $false \to$ too slow, so we set $l = mid + 1$.
  4. Termination
    • The loop ends when $l == r$, which is the minimum speed at which $canFinish$ flips from $false$ to $true$.
    • Return $r$.

 

Complexities

Time Complexity

  • Each binary‐search iteration does one $canFinish$ check in $O(n)$ ($n$ = number of piles).
  • Number of iterations $\approx \log_2 {(max(pile) - 1)} = O(\log M)$, where $M$ = size of largest pile.
  • Total: $O(n \cdot \log M)$.

 

Space Complexity

$O(1)$ extra memory (ignoring input storage).

 

Code on GitHub

Last updated 11 May 2025, 19:46 +0500 . history