Smallest positive integer that divides all array elements to generate quotients with sum not exceeding K | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findSmallestInteger ( int arr [ ] , int N , int K ) { int left = 1 ; int right = * max_element ( arr , arr + N ) ; 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 ; } int main ( ) { int arr [ ] = { 1 , 2 , 5 , 9 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; ; int K = 6 ; cout << findSmallestInteger ( arr , N , K ) ; }