Find maximum height to cut all chocolates horizontally such that at least K amount remains | Java program for the above approach ; 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
import java . util . * ; import java . util . Arrays ; class GFG { static int cal ( int arr [ ] , int mid ) { int chocolate = 0 ; for ( int i = 0 ; i < arr . length ; i ++ ) { if ( arr [ i ] >= mid ) chocolate += arr [ i ] - mid ; } return chocolate ; } static int maximumCut ( int arr [ ] , int K ) { int low = 0 ; int high = Arrays . stream ( arr ) . max ( ) . getAsInt ( ) ; while ( low <= high ) { int mid = ( low + high ) / 2 ; int 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 ; } public static void main ( String [ ] args ) { int K = 7 ; int arr [ ] = { 15 , 20 , 8 , 17 } ; System . out . println ( maximumCut ( arr , K ) ) ; } }