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;
}