Smallest positive integer that divides all array elements to generate quotients with sum not exceeding K | 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
def findSmallestInteger ( arr , N , K ) : NEW_LINE INDENT left = 1 NEW_LINE right = max ( arr ) NEW_LINE while ( left < right ) : NEW_LINE INDENT mid = ( left + right ) // 2 NEW_LINE sum = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT sum += ( arr [ i ] + mid - 1 ) // mid NEW_LINE DEDENT if ( sum > K ) : NEW_LINE INDENT left = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT right = mid NEW_LINE DEDENT DEDENT return left NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 2 , 5 , 9 ] NEW_LINE N = len ( arr ) NEW_LINE K = 6 NEW_LINE print ( findSmallestInteger ( arr , N , K ) ) NEW_LINE DEDENT