Minimum K such that sum of array elements after division by K does not exceed S | Java implementation of the approach ; Function to return the minimum value of k that satisfies the given condition ; Find the maximum element ; Lowest answer can be 1 and the highest answer can be ( maximum + 1 ) ; Binary search ; Get the mid element ; Calculate the sum after dividing the array by new K which is mid ; Search in the second half ; First half ; Driver code
class GFG { static int findMinimumK ( int a [ ] , int n , int s ) { int maximum = a [ 0 ] ; for ( int i = 0 ; i < n ; i ++ ) { maximum = Math . max ( maximum , a [ i ] ) ; } int low = 1 , high = maximum + 1 ; int ans = high ; while ( low <= high ) { int mid = ( low + high ) / 2 ; int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { sum += ( int ) ( a [ i ] / mid ) ; } if ( sum > s ) low = mid + 1 ; else { ans = Math . min ( ans , mid ) ; high = mid - 1 ; } } return ans ; } public static void main ( String [ ] args ) { int a [ ] = { 10 , 7 , 8 , 10 , 12 , 19 } ; int n = a . length ; int s = 27 ; System . out . println ( findMinimumK ( a , n , s ) ) ; } }