Value to be subtracted from array elements to make sum of all elements equals K | 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
def woodCollected ( height , n , m ) : NEW_LINE INDENT sum = 0 NEW_LINE for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT if ( height [ i ] - m <= 0 ) : NEW_LINE INDENT break NEW_LINE DEDENT sum += ( height [ i ] - m ) NEW_LINE DEDENT return sum NEW_LINE DEDENT def collectKWood ( height , n , k ) : NEW_LINE INDENT height = sorted ( height ) NEW_LINE low = 0 NEW_LINE high = height [ n - 1 ] NEW_LINE while ( low <= high ) : NEW_LINE INDENT mid = low + ( ( high - low ) // 2 ) NEW_LINE collected = woodCollected ( height , n , mid ) NEW_LINE if ( collected == k ) : NEW_LINE INDENT return mid NEW_LINE DEDENT if ( collected > k ) : NEW_LINE INDENT low = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT high = mid - 1 NEW_LINE DEDENT DEDENT return - 1 NEW_LINE DEDENT height = [ 1 , 2 , 1 , 2 ] NEW_LINE n = len ( height ) NEW_LINE k = 2 NEW_LINE print ( collectKWood ( height , n , k ) ) NEW_LINE