Koko Eating Bananas Leetcode Solution  

Difficulty Level Medium
Frequently asked in Facebook
algorithms Binary Search coding Interview interviewprep LeetCode LeetCodeSolutions

Problem statement  

In the problem ” Koko Eating Bananas” we are given an array of size n which contains the number of bananas in each pile. In one hour Koko can eat at most K bananas. If the pile contains less than K bananas in that case if Koko finishes all bananas of that pile then she cannot start eating bananas from another pile in the same hour.

Koko wants to eat all bananas within H hours. We are supposed to find the minimum value of K.

Example

piles = [30,11,23,4,20], H = 6
23

Explanation: 

leetcode solution to koko eating bananasPin

Please click Like if you loved this article?

Koko will eat bananas in this way to eat all bananas in 6 hours:

First hour: 23

Second hour: 7

Third hour: 11

Fourth hour: 23

Fifth hour: 4

Sixth hour: 20

Please click Like if you loved this article?

Approach for Koko Eating Bananas Leetcode Solution  

The first and the most important thing to solve this problem is to bring out observations. Here are a few observations for our search interval:

  1. Koko must eat at least one banana per hour. So this is the minimum value of K. let’s name it as Start
  2. We can limit the maximum number of bananas Koko can eat in one hour to the maximum number of bananas in a pile out of all the piles. So this is the maximum value of K. let’s name it as End.
See also
Insert into a Binary Search Tree Leetcode Solution

Now we have our search interval. Suppose the size of the interval is Length and the number of piles is n.  The naive approach could be to check for each value in the interval. if for that value of K Koko can eat all bananas in H hour successfully then pick the minimum of them. The time complexity for the naive approach will be Length*n in worst case.

We can improve the time complexity by using Binary Search in place of Linear Search.

The time complexity using the Binary Search approach will be log(Length)*n.

Implementation

C++ code for Koko Eating Bananas

#include <bits/stdc++.h>
using namespace std; 
       int minEatingSpeed(vector<int>& pile, int hour) {
        int left = 1, right = *max_element(pile.begin(),pile.end());;
        while (left < right) {
            int mid = (left + right) / 2, total = 0;
            for (int p : pile) total += (p + mid - 1) / mid;
            if (total > hour) left = mid + 1; else right = mid;
        }
        return left;
    }
int main() 
{ 
 vector<int> arr = {30,11,23,4,20}; 
 int H=6;                               
 cout<<minEatingSpeed(arr,H)<<endl;
 return 0;
}
23

Java code for Koko Eating Bananas

import java.util.Arrays; 
public class Tutorialcup {
    public static int minEatingSpeed(int[] piles, int H) {
        int left = 1, right =Arrays.stream(piles).max().getAsInt();
        while (left < right) {
            int mid = (left + right) / 2, total = 0;
            for (int p : piles) total += (p + mid - 1) / mid;
            if (total > H) left = mid + 1; else right = mid;
        }
        return left;
    }
  public static void main(String[] args) {
    int [] arr = {30,11,23,4,20}; 
     int H=6; 
    int ans= minEatingSpeed(arr,H);
    System.out.println(ans);
  }
}
23

Complexity Analysis of Koko Eating Bananas Leetcode Solution  

Time complexity

The time complexity of the above code is O(n*log(W)) because we are performing a binary search between one and W this takes logW time and for each value, in the binary search, we are traversing the piles array.  So the piles array is traversed logW times it makes the time complexity n*logW. Here n and W are the numbers of piles and the maximum number of bananas in a pile.

See also
Maximum path sum in a triangle

Space complexity

The space complexity of the above code is O(1) because we are using only a variable to store the answer.

References

Please click Like if you loved this article?

Please click Like if you loved this article?

Ads Blocker Image Powered by Code Help Pro
Ads Blocker Detected!!!

This website does not work properly with AdBlock. We have detected that you are using extensions to block ads. Please disable Adblocker to view the content.

Refresh