Daily bit(e) of C++ | Monkey eating bananas
Daily bit(e) of C++ #280, Common interview problem: Monkey eating bananas.
Today, we will look at a common C++ interview problem: Monkey eating bananas.
Given the count of bananas in piles as std::vector<size_t> and the number of hours before the monkey is discovered as size_t.
Return the most leisurely eating speed (bananas per hour) that allows the monkey to consume all bananas before it is discovered. The monkey will only eat from one pile each hour.
For example, for the input {2,1,4} and limit of 4 hours, the minimum speed is two bananas per hour.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/9nq77e7ad.
Solution
Let’s first understand the problem.
If we are given a specific speed, we can calculate the total time by summing up the times for each pile (since the monkey will not switch between piles mid-hour). A single pile will take (count-1)/speed+1 hours to be consumed.
To find our desired speed, we need to find the minimum speed such that the total sum of hours is less than or equal to our time limit.
Since we need to calculate the cost every time we take a guess, the complexity will be O(piles*guesses). The optimal algorithm for minimizing the number of guesses is binary search, leading to O(piles*log(max_bananas)).
