# Cut the Bamboo| CUTBAMBOO

Cut the Bamboo

Setter: Ayush Kumar
Tester: Ramandeep Singh
Editorialist: Ayush Kumar

Medium

# problem

Devansham Upadhyay, the King of Bamboo Forest, wants some bamboo for the winter season. He doesn’t like the cutting of forest but also needs some Bamboo. He needs a collection of K Bamboo and has asked you to cut all the Bamboo at maximum height H from the ground to satisfy the requirement. You will be provided with an array of size N containing the list of heights of Bamboo as h1, h2, ...hn. Find that maximum height H.

# Explanation

As we can observe by looking into its constrain which is <= 10^18 and there is a monotonic function form like for height h from 0 to 1e18, this is a binary search problem.

The results of the monotonic function look something like (F :-> false) (T:-> true) T T T T T T T T T T T T T T T T T T F F F F F F F F F F F F F F F F F

we have to find the last height h at which our function gives us true.

O(n x log(n))

# Solution

``````#include<bits/stdc++.h>
using namespace std;
#define int long long int
int n,k;
int a[1000000];

bool check(int m,int k)
{
int sum =0;
for(int i=1;i<=n;i++)
{
if(a[i]>m)
{
sum += (a[i]-m);
}
}

if(sum>=k){
return true;
}
return false;
}

void solve()
{
// n<=10^6
cin>>n>>k; //      k<= 10^18
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
int lo = 0,hi = 1e18,mid;
while(hi-lo>1)
{
mid = lo + (hi-lo)/2;
if(check(mid,k))
{
lo =  mid;
}
else
{
hi = mid-1;
}
}
if(check(hi,k))
{
cout<<hi;
}
else{
cout<<lo;
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
solve();
return 0;
}
``````