Minimum K such that sum of array elements after division by K does not exceed S | 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
def findMinimumK ( a , n , s ) : NEW_LINE INDENT maximum = a [ 0 ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT maximum = max ( maximum , a [ i ] ) NEW_LINE DEDENT low = 1 NEW_LINE high = maximum + 1 NEW_LINE ans = high NEW_LINE while ( low <= high ) : NEW_LINE INDENT mid = ( low + high ) // 2 NEW_LINE sum = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT sum += ( a [ i ] // mid ) NEW_LINE DEDENT if ( sum > s ) : NEW_LINE INDENT low = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT ans = min ( ans , mid ) NEW_LINE high = mid - 1 NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT a = [ 10 , 7 , 8 , 10 , 12 , 19 ] NEW_LINE n = len ( a ) NEW_LINE s = 27 NEW_LINE print ( findMinimumK ( a , n , s ) ) NEW_LINE