Find maximum height to cut all chocolates horizontally such that at least K amount remains | Function to find the sum of remaining chocolate after making the horizontal cut at height mid ; Stores the sum of chocolates ; Traverse the array arr [ ] ; If the height is at least mid ; Return the possible sum ; Function to find the maximum horizontal cut made to all the chocolates such that the sum of the remaining element is at least K ; Ranges of Binary Search ; Perform the Binary Search ; Find the sum of removed after making cut at height mid ; If the chocolate removed is same as the chocolate needed then return the height ; If the chocolate removed is less than chocolate needed then shift to the left range ; Otherwise , shift to the right range ; Return the possible cut ; Driver Code
function cal ( arr , mid ) { let chocolate = 0 for ( let i = 0 ; i < arr . length ; i ++ ) { if ( arr [ i ] >= mid ) chocolate += arr [ i ] - mid } return chocolate } function maximumCut ( arr , K ) { let low = 0 let high = arr [ 0 ] ; for ( let i = 1 ; i < arr . length ; i ++ ) { high = Math . max ( high , arr [ i ] ) ; } while ( low <= high ) { mid = Math . floor ( ( low + high ) / 2 ) ; chocolate = cal ( arr , mid ) if ( chocolate == K ) { return mid } else if ( chocolate < K ) { high = mid - 1 } else { low = mid + 1 if ( mid > high ) high = mid } } return high } let N = 4 ; let K = 7 ; let arr = [ 15 , 20 , 8 , 17 ] ; document . write ( maximumCut ( arr , K ) )