DAY 75 - 875. Koko Eating Bananas

Hey Guys!. It's day 75 and we are 3/4th done in our journey. I am back to my university so it's a little harder now to publish articles daily but I will try my best to complete the challenge.

Now let's back to the question. It's quite a famous one and an easy one as well.

Question: 875. Koko Eating Bananas

Koko loves to eat bananas. There are n piles of bananas, the ith 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.

Example 1:

• Input: piles = [3,6,7,11], h = 8
• Output: 4

Example 2:

• Input: piles = [30,11,23,4,20], h = 6
• Output: 23

Intuition and Question Breakdown:

• Let's start with understanding the question. I will try to make some observable points.
• Koko can at max eat from one pile and will dedicate the entire speed and unit time(hour here) to eat it even if it requires less time.
• Koko must finish all the piles and must do so in the given time h.
• We need to return the min value of k so that we can barely pass being caught by the guard because Koko is lazy.
• Sounds like, we need to find that one speed which barely saves us from the guard.
• How can we compute time required?. We simply take the ceil of every value in piles/speed of eating.
• Min speed koko can eat at is 1banana/hr and max is maxElement.
• This is because if we choose our speed to be maxElement and above it will always take piles.length() hours(minimum possible) to finish all bananas.
• Here to check all the speeds we can either use a for loop from 0 to maxElement.
• But incase that maxelement is very very large, it will give use TLE.
• So here we apply binary search. We can divide the values of K in such a way and apply binary Search accordingly to get the answer optimally.

Algorithm:

The approach involves the following steps:

1. Initialize the search range for the eating speed. The lower bound can be 1 (minimum possible speed), and the upper bound can be the maximum number of bananas in a single pile.

2. Perform a binary search within the given speed range. At each step, calculate the total number of hours required to consume all the bananas at the current speed using the count_banana function.

3. If the total hours required are less than or equal to the given h, it means the current eating speed is feasible. In this case, we move the upper bound of the search range to the left to explore slower eating speeds.

4. If the total hours required are greater than h, it means the current eating speed is not feasible. In this case, we move the lower bound of the search range to the right to explore faster eating speeds.

5. Repeat steps 2-4 until the lower bound is less than or equal to the upper bound.

6. The final value of the lower bound will represent the minimum eating speed that allows the person to finish eating within the given time constraint.

Code:

class Solution {
public:
long long count_banana(vector<int> &v,int num)
{
    long long sum=0;
    for(int i=0;i<v.size();i++)
    {
        sum+=ceil(v[i]/(double)num);
    }
    return sum;
}
    int minEatingSpeed(vector<int>& piles, int h) {
       int low=1;
       int high=*max_element(piles.begin(),piles.end());
       while(low<=high)
       {
           int mid=(low+high)/2;
           if(count_banana(piles,mid)<=h)
           {
               high=mid-1;
           }
           else{
               low=mid+1;
           }
       } 
       return low;
    }
};

Complexity Analysis:

Complexity Analysis: