Smallest positive integer that divides all array elements to generate quotients with sum not exceeding K | Java program to implement the above approach ; Function to find the smallest positive integer that divides array elements to get the sum <= K ; Stores minimum possible of the smallest positive integer satisfying the condition ; Stores maximum possible of the smallest positive integer satisfying the condition ; Apply binary search over the range [ left , right ] ; Stores middle element of left and right ; Stores sum of array elements ; Traverse the array ; Update sum ; If sum is greater than K ; Update left ; Update right ; Driver code
import java . util . * ; class GFG { static int findSmallestInteger ( int arr [ ] , int N , int K ) { int left = 1 ; int right = Arrays . stream ( arr ) . max ( ) . getAsInt ( ) ; while ( left < right ) { int mid = ( left + right ) / 2 ; int sum = 0 ; for ( int i = 0 ; i < N ; i ++ ) { sum += ( arr [ i ] + mid - 1 ) / mid ; } if ( sum > K ) { left = mid + 1 ; } else { right = mid ; } } return left ; } public static void main ( String [ ] args ) { int [ ] arr = { 1 , 2 , 5 , 9 } ; int N = arr . length ; int K = 6 ; System . out . println ( findSmallestInteger ( arr , N , K ) ) ; } }