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
def cal ( arr , mid ) : NEW_LINE INDENT chocolate = 0 NEW_LINE for i in arr : NEW_LINE INDENT if i >= mid : NEW_LINE INDENT chocolate += i - mid NEW_LINE DEDENT DEDENT return chocolate NEW_LINE DEDENT def maximumCut ( arr , K ) : NEW_LINE INDENT low = 0 NEW_LINE high = max ( arr ) NEW_LINE while low <= high : NEW_LINE INDENT mid = ( low + high ) // 2 NEW_LINE chocolate = cal ( arr , mid ) NEW_LINE if chocolate == K : NEW_LINE INDENT return mid NEW_LINE DEDENT elif chocolate < K : NEW_LINE INDENT high = mid - 1 NEW_LINE DEDENT else : NEW_LINE INDENT low = mid + 1 NEW_LINE if mid > high : NEW_LINE INDENT high = mid NEW_LINE DEDENT DEDENT DEDENT return high NEW_LINE DEDENT N , K = 4 , 7 NEW_LINE arr = [ 15 , 20 , 8 , 17 ] NEW_LINE print ( maximumCut ( arr , K ) ) NEW_LINE