Value to be subtracted from array elements to make sum of all elements equals K | C ++ implementation of the approach ; Function to return the amount of wood collected if the cut is made at height m ; Function that returns Height at which cut should be made ; Sort the heights of the trees ; The minimum and the maximum cut that can be made ; Binary search to find the answer ; The amount of wood collected when cut is made at the mid ; If the current collected wood is equal to the required amount ; If it is more than the required amount then the cut needs to be made at a height higher than the current height ; Else made the cut at a lower height ; Driver code
#include <bits/stdc++.h> NEW_LINE #include <iostream> NEW_LINE using namespace std ; int woodCollected ( int height [ ] , int n , int m ) { int sum = 0 ; for ( int i = n - 1 ; i >= 0 ; i -- ) { if ( height [ i ] - m <= 0 ) break ; sum += ( height [ i ] - m ) ; } return sum ; } int collectKWood ( int height [ ] , int n , int k ) { sort ( height , height + n ) ; int low = 0 , high = height [ n - 1 ] ; while ( low <= high ) { int mid = low + ( ( high - low ) / 2 ) ; int collected = woodCollected ( height , n , mid ) ; if ( collected == k ) return mid ; if ( collected > k ) low = mid + 1 ; else high = mid - 1 ; } return -1 ; } int main ( ) { int height [ ] = { 1 , 2 , 1 , 2 } ; int n = sizeof ( height ) / sizeof ( height [ 0 ] ) ; int k = 2 ; cout << collectKWood ( height , n , k ) ; return 0 ; }