Koko Eating Bananas

New·#875·Medium·Binary Search

Slowest eating speed that still beats the clock

Asked at:AmazonGoogleMetaBloomberg

Practice mode

Step

Initialization

Koko finishes a pile in ⌈pile / speed⌉ hours — she never moves on to another pile within the same hour, which is why the division rounds up. Eating faster can only reduce the total, so the hours are monotonic in the speed.

Recursion workspace

Binary Search on the Answer

Step 1 / 10init

100%

low

high

piles

Explanation

Speeds above 15 are pointless — she already finishes the largest pile in one hour — so the answer lies in 1…15.

step 1 / 10

Space play← → stepHome reset

TimeO(n log max)·SpaceO(1)

Binary Search on the Answer

1function calculateTotalHours(nums, hourly) {
2  let totalH = 0;
3  const n = nums.length;
4  for (let i = 0; i < n; i++) {
5    totalH += Math.ceil(nums[i] / hourly);
6  }
7  return totalH;
8}
9 
10function minimumRateToEatBananas(nums, h) {//low: 1high: 15
11  let low = 1, high = findMax(nums);
12 
13  while (low <= high) {
14    const mid = Math.floor((low + high) / 2);
15    const totalH = calculateTotalHours(nums, mid);
16 
17    // Fast enough — try slower
18    if (totalH <= h) {
19      high = mid - 1;
20    } else {
21      low = mid + 1;
22    }
23  }
24  return low;
25}

low1

high15

Command Palette

Koko Eating Bananas

Koko Eating Bananas