Koko Eating Bananas

JavaView on GFG

Problem Overview

Binary search on eating speed k.

See our study guide for structured GFG and LeetCode practice.

Intuition

Binary search on eating speed k. At speed k, hours needed = sum(ceil(pile/k)). Find minimum k where hours <= H.

Algorithm

1lo=1, hi=max(piles).
2Feasibility(k): sum(ceil(pile/k)) <= H.
3Return minimum feasible k.

Common Pitfalls

• ceil(pile/k) = (pile+k-1)/k in integer arithmetic. Binary search on speed, not on hours.

Koko Eating Bananas.java

Java

// Approach: Binary search on eating speed k. For each k, check if Koko finishes all piles in H hours.
// Time: O(n log(max_pile)) Space: O(1)
import java.util.*;

class Solution {
    public int kokoEat(int[] arr, int k) {
        Arrays.sort(arr);
        int ans = -1;
        int low = 1;
        int high = (int) 1e9;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (ispossible(arr, mid) <= k) {
                ans = mid;
                high = mid - 1;
            } else
                low = mid + 1;
        }

        return ans;
    }

    private int ispossible(int[] arr, int mid) {
        int ans = 0;
        for (int i = 0; i < arr.length; i++) {
            int cnt = arr[i] / mid;
            if (arr[i] % mid != 0)
                cnt++;

            ans += cnt;
        }
        
        return ans;
    }
}

Was this solution helpful?