Smallest number to make Array sum at most K by dividing each element | Java program to find the smallest number such that the sum of the array becomes less than or equal to K when every element of the array is divided by that number ; Function to find the smallest number such that the sum of the array becomes less than or equal to K when every element of the array is divided by that number ; Binary search between 1 and 10 ^ 9 ; Calculating the new sum after dividing every element by mid ; If after dividing by mid , if the new sum is less than or equal to limit move low to mid + 1 ; Else , move mid + 1 to high ; Returning the minimum number ; Driver Code
import java . util . * ; class GFG { static int findMinDivisor ( int arr [ ] , int n , int limit ) { int low = 0 , high = 1000000000 ; while ( low < high ) { int mid = ( low + high ) / 2 ; int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { sum += Math . ceil ( ( double ) arr [ i ] / ( double ) mid ) ; } if ( sum <= limit ) high = mid ; else low = mid + 1 ; } return low ; } public static void main ( String args [ ] ) { int arr [ ] = { 2 , 3 , 4 , 9 } ; int N = arr . length ; int K = 6 ; System . out . println ( findMinDivisor ( arr , N , K ) ) ; } }