Dojo Eating apples – A Binary search problem in C++

This problem is about how can we use binary search algorithm and use it to solve complex problems we will learn about the concepts and algorithm used and then will see its implementation in C++.

Problem description

There are N piles of apples the i-th pile has Piles[i] apples. The guards have gone and will come back in H hours. Dojo can decide her apple-per-hour eating speed of K. Each hour, she chooses some pile of apple and eats K apples from that pile. If the pile has less than K apple, she eats all of them instead, and won’t eat any more apples during this hour. Dojo wants to finish eating all the apples before the guards come back. Return the minimum integer K such that she can eat all the apples 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 = 5

Output:

 30

Example 3:

Input:

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

Output:

 23

Constraints:

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

Approach 

Now as mentioned in the problem statement we had to return the minimum value of K (minimum number of bananas Koko should eat to finish eating within H hours). Now according to constraints we see that the minimum value of H is piles length so the maximum value of K can be the maximum element of the array as then in each hour Koko has to eat each pile to finish eating within H hours and minimum value of K can be 1 if only one banana is there and one pile. Now we have found the minimum and maximum value K can take now we can proceed further as we have got the range space so we are sure that our answer will lie in this range only

Minimum value of K = 1

Maximum value of K = maximum value from array

Now the problem seems to be solved by binary search algorithm

Binary search 

It is a searching algorithm applied on sorted array by repeatedly dividing the search interval in half.we First begin with whole interval then divide the search interval in half If the value of the search key is less than the mid value of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty

int binsearch(int arr[], int l, int r, int x)  // l is low value, r is high value and x is the element to be searched
{ 
     while (l <= r) {  
        int m = l + (r - l) / 2;  // calculating mid value
  
        // Check if x is present at mid 
        if (arr[m] == x) 
            return m; 
  
        // If x greater, ignore left half 
        if (arr[m] < x) 
            l = m + 1; 
  
        // If x is smaller, ignore right half 
        else
            r = m - 1; 
    } 
  
    // if element is not present then return -1 indicating x is not present in array 
    return -1; 
}

Now in our problem we will be applying the same algorithm and calculate the value of K. For every mid value calculated we will see does this satisfy the given condition i.e finishing the apples within H hours if yes then we will narrow the search space and decrease the high value (as we want the minimum answer) and if it is not possible to finish the apples within H hours for a given mid-value we had to increase the low value to satisfy the condition for that we need one helper function here which will calculate and return the hours needed to finish eating all piles of apple for a given mid-value

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 int helper(vector<int>piles,int mid)
{   int cnt=0;
        for(int i=0;i<piles.size();i++){  // calculating for a given value of K(mid) how much time is needed to finish eating apple
            int div=((double)piles[i]/mid);
            int rem=(piles[i]%mid);
            if(rem!=0)
                cnt++;
            cnt+=div;

     }

     return cnt; // cnt stores the hour needed for a given value of mid
}

int minEatingSpeed(vector<int>& piles, int H) {
int l=1;
int r=*max_element(piles.begin(),piles.end()); //we have taken this high because we want to get the minimum hour so we need to find the ceiling value

        while(l<r)
        {
            int mid=(l+r)/2;
            if(helper(piles,mid)<=H)
                r=mid;
            else
                l=mid+1;
        }
        return r;
}

int main()
{
int n;
cin>>n;
vector<int>arr(n);
for(int i=0;i<n;i++)
cin>>arr[i];
int H;
cin>>H;
int ans=minEatingSpeed(arr,H);
cout<<ans;

return 0;
}

Sample Case

For the given input piles = [3,6,7,11], H = 8

if K=4, then Koko will eat 4 apples per hour so in 1st hour he will eat 3 apples then in 2nd hour he will eat 4 apples then 6-4=2 apples left so again 1 hour needed therefore, to eat pile one 1 hour needed, for 2nd pile 2 hours needed, for 3rd pile 2 hours needed for 4th pile 3 hours needed . So 1+2+2+3=8 hours needed to finish eating apples if he eats 4 apples per hour and this is the minimum answer for this case.

Hope you understand the implementation and algorithm used ! Thank you

Leave a Reply

Your email address will not be published. Required fields are marked *