Minimize Steps required to obtain Sorted Order of an Array | Function to find GCD of two numbers ; Function to calculate the LCM of array elements ; Initialize result ; Function to find minimum steps required to obtain sorted sequence ; Inititalize dat [ ] array for Direct Address Table . ; Calculating steps required for each element to reach its sorted position ; Calculate LCM of the array ; Driver Code
def gcd ( a , b ) : NEW_LINE INDENT if ( b == 0 ) : NEW_LINE INDENT return a NEW_LINE DEDENT return gcd ( b , a % b ) NEW_LINE DEDENT def findlcm ( arr , n ) : NEW_LINE INDENT ans = 1 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT ans = ( ( arr [ i ] * ans ) // ( gcd ( arr [ i ] , ans ) ) ) NEW_LINE DEDENT return ans NEW_LINE DEDENT def minimumSteps ( arr , n ) : NEW_LINE INDENT dat = [ 0 ] * ( n + 1 ) NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT dat [ arr [ i - 1 ] ] = i NEW_LINE DEDENT b = [ 0 ] * ( n + 1 ) NEW_LINE j = 0 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT c = 1 NEW_LINE j = dat [ i ] NEW_LINE while ( j != i ) : NEW_LINE INDENT c += 1 NEW_LINE j = dat [ j ] NEW_LINE DEDENT b [ i ] = c NEW_LINE DEDENT print ( findlcm ( b , n ) ) NEW_LINE DEDENT arr = [ 5 , 1 , 4 , 3 , 2 , 7 , 6 ] NEW_LINE N = len ( arr ) NEW_LINE minimumSteps ( arr , N ) NEW_LINE