Minimize Steps required to obtain Sorted Order of an Array | C ++ Program to implement the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int gcd ( int a , int b ) { if ( b == 0 ) return a ; return gcd ( b , a % b ) ; } int findlcm ( int arr [ ] , int n ) { int ans = 1 ; for ( int i = 1 ; i <= n ; i ++ ) ans = ( ( ( arr [ i ] * ans ) ) / ( gcd ( arr [ i ] , ans ) ) ) ; return ans ; } void minimumSteps ( int arr [ ] , int n ) { int i , dat [ n + 1 ] ; for ( i = 1 ; i <= n ; i ++ ) dat [ arr [ i - 1 ] ] = i ; int b [ n + 1 ] , j = 0 , c ; for ( i = 1 ; i <= n ; i ++ ) { c = 1 ; j = dat [ i ] ; while ( j != i ) { c ++ ; j = dat [ j ] ; } b [ i ] = c ; } cout << findlcm ( b , n ) ; } int main ( ) { int arr [ ] = { 5 , 1 , 4 , 3 , 2 , 7 , 6 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; minimumSteps ( arr , N ) ; return 0 ; }