Binary search on the answer

Medium TimeO(n log m) SpaceO(1)

Koko has piles of bananas and limit hours before the guards return. At a chosen speed she eats from one pile an hour — finishing it, or taking that many from it — and never starts a second pile in the same hour, so an hour spent on a pile smaller than her speed is partly wasted. Return the slowest whole-banana speed that still clears every pile in time. There are always at least as many hours as piles, so some speed always works.

Examples

Example 1

Input
piles = [3, 6, 7, 11]limit = 8
Output
4
At 4 an hour the piles take 1 + 2 + 2 + 3 = 8 hours, exactly the limit; at 3 they take 10.

Example 2

Input
piles = [3, 6, 7, 11]limit = 4
Output
11
Four hours for four piles is one pile an hour, so the speed has to reach the largest pile.

The Code

function hoursNeeded(piles, speed) {
  let hours = 0;
  for (let i = 0; i < piles.length; i++) {
    hours += Math.ceil(piles[i] / speed);
  }
  return hours;
}
function minEatingSpeed(piles, limit) {
  let low = 1;
  let high = Math.max.apply(null, piles);
  while (low < high) {
    const mid = Math.floor((low + high) / 2);
    if (hoursNeeded(piles, mid) <= limit) high = mid;
    else low = mid + 1;
  }
  return low;
}
minEatingSpeed([3, 6, 7, 11], 8);
Done

The first 18 calls, of 30. This one does not fit on a page.

Step through minEatingSpeed([3, 6, 7, 11], 8) call by call

More like this

All searching examples (8) →