Smallest possible integer K such that ceil of each Array element when divided by K is at most M | C ++ program for the above approach ; Function to check if the sum of ceil values of the arr [ ] for the K value is at most M or not ; Stores the sum of ceil values ; Update the sum ; Return true if sum is less than or equal to M , false otherwise ; Function to find the smallest possible integer K such that ceil ( arr [ 0 ] / K ) + ceil ( arr [ 1 ] / K ) + ... . + ceil ( arr [ N - 1 ] / K ) is less than or equal to M ; Stores the low value ; Stores the high value ; Stores the middle value ; Update the mid value ; Check if the mid value is K ; Update the low value ; Update the high value ; Check if low is K or high is K and return it ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isvalid ( int arr [ ] , int K , int N , int M ) { int sum = 0 ; for ( int i = 0 ; i < N ; i ++ ) { sum += ( int ) ceil ( arr [ i ] * 1.0 / K ) ; } return sum <= M ; } int smallestValueForK ( int arr [ ] , int N , int M ) { int low = 1 ; int high = * max_element ( arr , arr + N ) ; int mid ; while ( high - low > 1 ) { mid = ( high + low ) / 2 ; if ( ! isvalid ( arr , mid , N , M ) ) low = mid + 1 ; else high = mid ; } return isvalid ( arr , low , N , M ) ? low : high ; } int main ( ) { int arr [ ] = { 4 , 3 , 2 , 7 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int M = 5 ; cout << smallestValueForK ( arr , N , M ) ; return 0 ; }