Table of contents
1.
Introduction
2.
What is Koko Eating Bananas
3.
Problem Statement
4.
Solution-1(Naive Approach)
4.1.
Algorithm
4.2.
Implementation
4.3.
Complexity
5.
Solution-2(Binary-Search Approach)
5.1.
Algorithm
5.2.
Implementation
5.3.
Complexity
6.
Frequently Asked Questions
6.1.
When is Binary Search applied?
6.2.
On which parameter is Binary Search apple?
6.3.
What is the Time Complexity of Binary Search?
6.4.
How does Koko eating bananas work?
7.
Conclusion
Last Updated: May 4, 2024
Medium

Koko Eating Bananas

Author Yogesh Kumar
2 upvotes
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Today’s problem, i.e., –Koko Eating Bananas,” is highly asked in product-based companies like Amazon, Google, and Microsoft.

We’ll go over all the methods, including brute force and the most efficient way to solve this problem.

Koko Eating Bananas

What is Koko Eating Bananas

Koko eating bananas is a problem in which Koko, a monkey, is given 'n' piles of bananas. Each pile 'i' has 'a[i]' bananas. An integer 'h' represents the time (in hours) for Koko to eat all bananas. Koko eats 'k' bananas per hour. Find the minimum 'k' to ensure Koko finishes eating within 'h' hours. 

Let us clearly understand this problem statement.

Problem Statement

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 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.

 

Eg: Input: piles:[ 3 , 6 , 7 , 11 ] and h=8

Output: 4

  • 1 <= piles.length <= 10^4
  • piles.length <= h <= 10^9
  • 1 <= piles[i] <= 10^9

 

Now talking about the problem statement, KoKo eats the Bananas, and n piles of bananas are stored in piles array. Koko has to eat the bananas with k speed such that all the bananas should be eaten in less than or equal to h hours. We have to find the minimum value of k for the solution.

 

Let's take an example and explain it for better understanding.

 

E.g.:  piles:[ 3, 6, 7, 11 ] and h=8

 

If we see the array of piles of bananas stored at the ith location for n number of piles and having hours value is 8.

 

Approach: let’s iterate with a minimal value of K, i.e., 1, and iterate through to go till the maximum value of h given in the constraint and check for all k values. Is it able to eat all the bananas present in the piles or not. We use the formula (piles[i]-1)/k+1 for the time calculation in hours for finding the duration to eat the bananas in the ith piles entirely with the particular k value.

 

  1. K=1, then  3+6>8 at the 1st index position itself for 0 based indexing hours increases.
  2. K=2, then 2+3+4>8 at the 2nd index position itself, the current time limit exceeds the deadline.
  3. K=3 then 1+2+3+4>8 at the 3rd index position itself,  the current time limit exceeds the deadline.
  4. K=4 then 1+2+2+2<8 by taking the value of k=4, then we found the value of the complete time duration taken by Koko to eat all the banana piles is 7, which is less than 8, so guards do not come. 
  5. Hence K=4 is a suitable value for the solution of the problem.

 

Solution-1(Naive Approach)

In this approach, we use the brute-force approach or naive approach solution for computing the solution of code, as it's a brute force solution, so Time Limit Exceed in this case.

Algorithm

  1. Initialize the minimum value of k=1 at the first step.
  2. Run a loop for till the maximum value of h is given in constraint.
  3. Calculate the time required for each ith position pile for Koko to eat.
  4. We also keep track of conditional statement checks; it does not exceed the h value.
  5. If all the bananas present in piles are empty and we also check if time<=h, then we return a particular h value because it requires the minimum value of k.

Implementation

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int k=1;
            for(;k<1_000_000_001;k++){
                    int time=0;
                    for(int p:piles){
                            time+=(p-1)/k+1;
                            if(time>h) break;
                    }
                    if(time<=h){
                            break;
                    }
            }
            return k;
    }
}

Complexity

Complexity using Naive approach, as we see the highest value for hours limit is H hours, for selecting K value the outer loop runs for O(H)  from the start point from 1 to H for K, i.e., K=1 to H. Now for checking each K value, we iterate through the length of piles array of size N. So Overall time Complexity of the Solution is O(N*H), and we are not using any extra space here, so it's O(1). 

Time Complexity :O(N*H) and Space Complexity O(1).

Solution-2(Binary-Search Approach)

In this solution, we optimized from Naive to Binary Search  Approach in Time Complexity.

Algorithm

  1. Use the concept of Binary Search for choosing the value of k.
  2. We choose the k from 1 to the highest of h, i.e., 10^9.
  3. We run a while loop from low<high and calculate the mid-value.
  4. The idea behind the mid is if the mid-value selected for K has K/mid (time>h), then we have to choose from mid+1 not to move back, to mid which reduces the iteration step.
  5. Then we keep another function, isPossible to check if we have found the particular K or not as for the same manner for time calculation of each pile at ith and gets adding all these together if it time<=h then return true else false.
  6. Then we return the answer stored as a present low value.

Implementation

class Solution {
    public boolean isPossible(int[] piles,int h,int k){
            int time=0;
            for(int p:piles){
                  time+=(p-1)/k+1;
                  if(time>h) break;
            }
            return time<=h;
    }
    public int minEatingSpeed(int[] piles, int h) {
        int low=1,high=1_000_000_000;
          while(low<high){
                  int mid=low + (high-low)/2;
                  if(isPossible(piles,h,mid)){
                          high=mid;
                  }
                  else{
                          low=mid+1;
                  }
          }
          return low;
    }
}

Complexity

The complexity of the Binary Search Approach for the problem as for H seems to have the highest number of the hours ‘h’. Then we perform Binary Search over it, which is done in log(H) times, now for running the loop in an over piles array as the length of the array of size of N.We are perform step over each time for whenever the value of k is chosen for it, so the Time Complexity of the solution is O(N*log(H)). For Space Complexity, we are not using any extra space, so it's O(1).

See more, euclid gcd algorithm

Frequently Asked Questions

When is Binary Search applied?

It's only applied when the array is Sorted.

On which parameter is Binary Search apple?

On the hour’s range for selecting the value of K, sorted from 1 to 10^9.

What is the Time Complexity of Binary Search?

O(log(N)) is the time complexity of binary search.

How does Koko eating bananas work?

Koko has n hours to eat all the bananas before the guard returns, and she can set a constant eating speed of m bananas per hour. At each hour, she eats m bananas from a pile; if the pile has fewer than m bananas, she'll finish that pile and then stop eating for that hour.

Conclusion

We learned the application of Binary Search, how it reduced the Time Complexity of the problem from O(N*H) to O(N*log(H)). Implementation of Binary Search is also presented through the code with regards to solving the problem.

Live masterclass