Smallest number to make Array sum at most K by dividing each element | Python3 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
from math import ceil NEW_LINE def findMinDivisor ( arr , n , limit ) : NEW_LINE INDENT low = 0 NEW_LINE high = 10 ** 9 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 += ceil ( arr [ i ] / mid ) NEW_LINE DEDENT if ( sum <= limit ) : NEW_LINE INDENT high = mid NEW_LINE DEDENT else : NEW_LINE INDENT low = mid + 1 NEW_LINE DEDENT DEDENT return low NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 2 , 3 , 4 , 9 ] NEW_LINE N = len ( arr ) NEW_LINE K = 6 NEW_LINE print ( findMinDivisor ( arr , N , K ) ) NEW_LINE DEDENT