 # Easy C++ solution using binary search with proper explanation

#1
``````// Function to check wheather it is possible to cut wood pieces of total length >= 'wood_length' with a sawblade having a height = 'height'
bool is_valid(vector<int>&tree,long long int wood_length,long long int height)
{
long long int sum=0;
for(int i=0;i<tree.size();i++)
{
// If the tree height is greater than the sawblade height only then we can cut a piece from it.
if((long long int)tree[i]>=height)
{
sum+=(tree[i]-height); // Add the piece length to sum
}
}
// If at the end the total length of the wood pieces is greater than 'height'
// only then it possible to cut wood pieces of total length >= 'wood_length'
// otherwise it is impossible.
return sum>=wood_length;
}
int Solution::solve(vector<int> &A, int B)
{
long long int start=0,end=0,n=A.size(),ans=-1;
//Here start = starting point of binary search. It means the least possible length of sawblade
//Here end = ending point of binary search. It means the maximum possible length of sawblade
for(int i=0;i<n;i++)
{
// maximum possible length of sawblade is the maximum tree height. Cause beyond that there will be no tree.
end=max(end,(long long int)A[i]);
}
while(start<=end)
{
long long int mid=start+((end-start)/2);
// If it is possible to cut at least B length of wood with sawblade height = mid
// store the current sawblade height in ans and try to minimise the sawblade by taking start=mid+1
if(is_valid(A,B,mid))
{
ans=mid;
start=mid+1;
}
// If it is not possible at least B length of wood with sawblade height = mid,
// obviously we've to decrease the sawblade height so that the length of wood piece increases.
else
{
end=mid-1;
}
}
return ans;
}

``````