Koko Eating Bananas
Medium About 20 min Free, no account needed
The slowest eating speed that still finishes every pile in time.
The brief
Koko has piles[i] bananas in each pile and h hours. Each hour she picks one
pile and eats speed bananas from it (a smaller pile still costs the full
hour). Return the minimum integer speed that finishes all piles within h
hours.
The obvious approach tries speed 1, 2, 3, ... until one works. The hidden test
needs a speed of about one billion, so a step-by-step search is far too slow.
Note that the answer lies in 1..max(piles), and if a given speed finishes in
time then every higher speed does too, so you can narrow the range far faster
than one step at a time.
Starter code
using System;
public class Solution
{
// TODO: return the minimum integer speed finishing all piles within h hours.
public long MinEatingSpeed(long[] piles, long h)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
Related guides
What it practices
- Binary search on the answer
- Search the space of candidate answers when feasibility is monotonic.
Do these first
Related katas
- Cutting Ribbons Medium Free The longest equal piece length that still yields k pieces.
- Minimum Days to Make Bouquets Medium Free Earliest day enough adjacent flowers have bloomed for all the bouquets.
- Ship Packages Within D Days Medium Free Smallest ship capacity that delivers the conveyor belt on schedule.
- Integer Square Root Easy Free Floor of the square root, found without floating point.