LeetMotion
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.
1 <= piles.length <= 10⁴piles.length <= h <= 10⁹1 <= piles[i] <= 10⁹We know Koko must logically eat at least 1 banana per hour, and at most she needs to eat max(piles) per hour (because she can only consume 1 pile per hour anyway!). We can linearly test every possible speed k starting from 1 until we find the first rate where the total hours is <= h.
k from 1 to max(piles).k, iterate through all piles and calculate the total hours required: total = sum(ceil(p / k)).total <= h, we immediately return k because it's the smallest valid speed.Thoughts: Testing every single integer between 1 and a billion could result in TLE. The search space `1` to `max(P)` is inherently sorted. This is a massive clue!
Instead of doing linear search from 1 to max(piles), we can do a standard Binary Search over this sequence of potential answer values. This changes the scaling factor of testing speeds from $O(M)$ to $O(\log M)$ operations.
L = 1 and R = max(piles).k = (L + R) // 2.k by summing up math.ceil(pile / k) across the array.hours <= h, Koko successfully finished in time! We record k as a valid answer, but try to find an even smaller speed by limiting our search to the left half: R = k - 1.hours > h, she was too slow. We must logically increase her speed, meaning the answer is strictly in the right half: L = k + 1.
Discussion
…