Maximum elements that can be made equal with k updates | Function to calculate the maximum number of equal elements possible with atmost K increment of values . Here we have done sliding window to determine that whether there are x number of elements present which on increment will become equal . The loop here will run in fashion like 0. . . x - 1 , 1. . . x , 2. . . x + 1 , ... . , n - x - 1. . . n - 1 ; It can be explained with the reasoning that if for some x number of elements we can update the values then the increment to the segment ( i to j having length -> x ) so that all will be equal is ( x * maxx [ j ] ) this is the total sum of segment and ( pre [ j ] - pre [ i ] ) is present sum So difference of them should be less than k if yes , then that segment length ( x ) can be possible return true ; sort the array in ascending order ; Initializing the prefix array and maximum array ; Calculating prefix sum of the array ; Calculating max value upto that position in the array ; Binary search applied for computation here ; printing result ; Driver Code
def ElementsCalculationFunc ( pre , maxx , x , k , n ) : NEW_LINE INDENT i = 0 NEW_LINE j = x NEW_LINE while j <= n : NEW_LINE INDENT if ( x * maxx [ j ] - ( pre [ j ] - pre [ i ] ) <= k ) : NEW_LINE INDENT return True NEW_LINE DEDENT i += 1 NEW_LINE j += 1 NEW_LINE DEDENT return False NEW_LINE DEDENT def MaxNumberOfElements ( a , n , k ) : NEW_LINE INDENT a . sort ( ) NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT pre [ i ] = 0 NEW_LINE maxx [ i ] = 0 NEW_LINE DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT pre [ i ] = pre [ i - 1 ] + a [ i - 1 ] NEW_LINE maxx [ i ] = max ( maxx [ i - 1 ] , a [ i - 1 ] ) NEW_LINE DEDENT l = 1 NEW_LINE r = n NEW_LINE while ( l < r ) : NEW_LINE INDENT mid = ( l + r ) // 2 NEW_LINE if ( ElementsCalculationFunc ( pre , maxx , mid - 1 , k , n ) ) : NEW_LINE INDENT ans = mid NEW_LINE l = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT r = mid - 1 NEW_LINE DEDENT DEDENT print ( ans ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 2 , 4 , 9 ] NEW_LINE n = len ( arr ) NEW_LINE k = 3 NEW_LINE MaxNumberOfElements ( arr , n , k ) NEW_LINE DEDENT