Minimum increments to convert to an array of consecutive integers | Function that return true if the required array can be generated with m as the last element ; Build the desired array ; Check if the given array can be converted to the desired array with the given operation ; Function to return the minimum number of operations required to convert the given array to an increasing AP series with common difference as 1 ; Apply Binary Search ; If array can be generated with mid as the last element ; Current ans is mid ; Check whether the same can be achieved with even less operations ; Build the desired array ; Calculate the number of operations required ; Return the number of operations required ; Driver code
def check ( m , n , arr ) : NEW_LINE INDENT desired = [ 0 ] * n ; NEW_LINE for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT desired [ i ] = m ; NEW_LINE m -= 1 ; NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT if ( arr [ i ] > desired [ i ] or desired [ i ] < 1 ) : NEW_LINE INDENT return False ; NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT def minOperations ( arr , n ) : NEW_LINE INDENT start = arr [ n - 1 ] ; NEW_LINE end = max ( arr ) + n ; NEW_LINE max_arr = 0 ; NEW_LINE while ( start <= end ) : NEW_LINE INDENT mid = ( start + end ) // 2 ; NEW_LINE if ( check ( mid , n , arr ) ) : NEW_LINE INDENT max_arr = mid ; NEW_LINE end = mid - 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT start = mid + 1 ; NEW_LINE DEDENT DEDENT desired = [ 0 ] * n ; NEW_LINE for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT desired [ i ] = max_arr ; NEW_LINE max_arr -= 1 ; NEW_LINE DEDENT operations = 0 ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT operations += ( desired [ i ] - arr [ i ] ) ; NEW_LINE DEDENT return operations ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 4 , 4 , 5 , 5 , 7 ] ; NEW_LINE n = len ( arr ) ; NEW_LINE print ( minOperations ( arr , n ) ) ; NEW_LINE DEDENT