Maximize value at Kth index to create N size array with adjacent difference 1 and sum less than M | Function to calculate maximum value that can be placed at the Kth index in a distribution in which difference of adjacent elements is less than 1 and total sum of distribution is M . ; Variable to store final answer ; Variables for binary search ; Binary search ; Variable for binary search ; Variable to store total sum of array ; Number of indices on the left excluding the Kth index ; Number of indices on the left excluding the Kth index ; Add mid to final sum ; Distribution on left side is possible ; Sum of distribution on the left side ; Sum of distribution on the left side with ( L - mid ) 1 s ; Distribution on right side is possible ; Sum of distribution on the right side ; Sum of distribution on the left side with ( R - mid ) 1 s ; Distribution is valid ; Return answer ; Input ; Function call
def calculateMax ( N , M , K ) : NEW_LINE INDENT ans = - 1 NEW_LINE low = 0 NEW_LINE high = M NEW_LINE while ( low <= high ) : NEW_LINE INDENT mid = ( low + high ) / 2 NEW_LINE val = 0 NEW_LINE L = K - 1 NEW_LINE R = N - K NEW_LINE val += mid NEW_LINE if ( mid >= L ) : NEW_LINE INDENT val += ( L ) * ( 2 * mid - L - 1 ) / 2 NEW_LINE DEDENT else : NEW_LINE INDENT val += mid * ( mid - 1 ) / 2 + ( L - mid ) NEW_LINE DEDENT if ( mid >= R ) : NEW_LINE INDENT val += ( R ) * ( 2 * mid - R - 1 ) / 2 NEW_LINE DEDENT else : NEW_LINE INDENT val += mid * ( mid - 1 ) / 2 + ( R - mid ) NEW_LINE DEDENT if ( val <= M ) : NEW_LINE INDENT ans = max ( ans , mid ) NEW_LINE low = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT high = mid - 1 NEW_LINE DEDENT DEDENT return int ( ans ) NEW_LINE DEDENT N = 7 NEW_LINE M = 100 NEW_LINE K = 6 NEW_LINE print ( calculateMax ( N , M , K ) ) ; NEW_LINE