Given an array arr[] consisting of a permutation of integers [1, N], derived by rearranging the sorted order [1, N], the task is to find the minimum number of steps after which the sorted order [1, N] is repeated, by repeating the same process by which arr[] is obtained from the sorted sequence at each step.
Examples:
Input: arr[ ] = {3, 6, 5, 4, 1, 2}
Output: 6
Explanation:
Increasing Permutation: {1, 2, 3, 4, 5, 6}
Step 1 : arr[] = {3, 6, 5, 4, 1, 2} (Given array)
Step 2 : arr[] = {5, 2, 1, 4, 3, 6}
Step 3 : arr[] = {1, 6, 3, 4, 5, 2}
Step 4 : arr[] = {3, 2, 5, 4, 1, 6}
Step 5 : arr[] = {5, 6, 1, 4, 3, 2}
Step 6 : arr[] = {1, 2, 3, 4, 5, 6} (Increasing Permutation)
Therefore, the total number of steps required are 6.
Input: arr[ ] = [5, 1, 4, 3, 2]
Output: 6
Approach:
This problem can be solved simply by using the concept of Direct Addressing. Follow the steps given below to solve the problem:
- Initialize an array dat[] for direct addressing.
- Iterate over [1, N] and calculate the difference of the current index of every element from its index in the sorted sequence.
- Calculate the LCM of the array dat[].
- Now, print the obtained LCM as the minimum steps required to obtain the sorted order.
Below is the implementation of the above approach:
C++14
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find // GCD of two numbers int gcd( int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to calculate the // LCM of array elements int findlcm( int arr[], int n) { // Initialize result int ans = 1; for ( int i = 1; i <= n; i++) ans = (((arr[i] * ans)) / (gcd(arr[i], ans))); return ans; } // Function to find minimum steps // required to obtain sorted sequence void minimumSteps( int arr[], int n) { // Initialize dat[] array for // Direct Address Table. int i, dat[n + 1]; for (i = 1; i <= n; i++) dat[arr[i - 1]] = i; int b[n + 1], j = 0, c; // Calculating steps required // for each element to reach // its sorted position for (i = 1; i <= n; i++) { c = 1; j = dat[i]; while (j != i) { c++; j = dat[j]; } b[i] = c; } // Calculate LCM of the array cout << findlcm(b, n); } // Driver Code int main() { int arr[] = { 5, 1, 4, 3, 2, 7, 6 }; int N = sizeof (arr) / sizeof (arr[0]); minimumSteps(arr, N); return 0; } |
Java
// Java program to implement // the above approach class GFG{ // Function to find // GCD of two numbers static int gcd( int a, int b) { if (b == 0 ) return a; return gcd(b, a % b); } // Function to calculate the // LCM of array elements static int findlcm( int arr[], int n) { // Initialize result int ans = 1 ; for ( int i = 1 ; i <= n; i++) ans = (((arr[i] * ans)) / (gcd(arr[i], ans))); return ans; } // Function to find minimum steps // required to obtain sorted sequence static void minimumSteps( int arr[], int n) { // Initialize dat[] array for // Direct Address Table. int i; int dat[] = new int [n + 1 ]; for (i = 1 ; i <= n; i++) dat[arr[i - 1 ]] = i; int b[] = new int [n + 1 ]; int j = 0 , c; // Calculating steps required // for each element to reach // its sorted position for (i = 1 ; i <= n; i++) { c = 1 ; j = dat[i]; while (j != i) { c++; j = dat[j]; } b[i] = c; } // Calculate LCM of the array System.out.println(findlcm(b, n)); } // Driver code public static void main(String[] args) { int arr[] = { 5 , 1 , 4 , 3 , 2 , 7 , 6 }; int N = arr.length; minimumSteps(arr, N); } } // This code is contributed by rutvik_56 |
Python3
# Python3 program to implement # the above approach # Function to find # GCD of two numbers def gcd(a, b): if (b = = 0 ): return a return gcd(b, a % b) # Function to calculate the # LCM of array elements def findlcm(arr, n): # Initialize result ans = 1 for i in range ( 1 , n + 1 ): ans = ((arr[i] * ans) / / (gcd(arr[i], ans))) return ans # Function to find minimum steps # required to obtain sorted sequence def minimumSteps(arr, n): # Initialize dat[] array for # Direct Address Table. dat = [ 0 ] * (n + 1 ) for i in range ( 1 , n + 1 ): dat[arr[i - 1 ]] = i b = [ 0 ] * (n + 1 ) j = 0 # Calculating steps required # for each element to reach # its sorted position for i in range ( 1 , n + 1 ): c = 1 j = dat[i] while (j ! = i): c + = 1 j = dat[j] b[i] = c # Calculate LCM of the array print (findlcm(b, n)) # Driver Code arr = [ 5 , 1 , 4 , 3 , 2 , 7 , 6 ] N = len (arr) minimumSteps(arr, N) # This code is contributed by Shivam Singh |
C#
// C# program to implement // the above approach using System; class GFG{ // Function to find // GCD of two numbers static int gcd( int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to calculate the // LCM of array elements static int findlcm( int []arr, int n) { // Initialize result int ans = 1; for ( int i = 1; i <= n; i++) ans = (((arr[i] * ans)) / (gcd(arr[i], ans))); return ans; } // Function to find minimum steps // required to obtain sorted sequence static void minimumSteps( int []arr, int n) { // Initialize dat[] array for // Direct Address Table. int i; int []dat = new int [n + 1]; for (i = 1; i <= n; i++) dat[arr[i - 1]] = i; int []b = new int [n + 1]; int j = 0, c; // Calculating steps required // for each element to reach // its sorted position for (i = 1; i <= n; i++) { c = 1; j = dat[i]; while (j != i) { c++; j = dat[j]; } b[i] = c; } // Calculate LCM of the array Console.WriteLine(findlcm(b, n)); } // Driver code public static void Main(String[] args) { int []arr = { 5, 1, 4, 3, 2, 7, 6 }; int N = arr.Length; minimumSteps(arr, N); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // JavaScript program for the above approach // Function to find // GCD of two numbers function gcd(a, b) { if (b == 0) return a; return gcd(b, a % b); } // Function to calculate the // LCM of array elements function findlcm(arr, n) { // Initialize result let ans = 1; for (let i = 1; i <= n; i++) ans = (((arr[i] * ans)) / (gcd(arr[i], ans))); return ans; } // Function to find minimum steps // required to obtain sorted sequence function minimumSteps(arr, n) { // Initialize dat[] array for // Direct Address Table. let i; let dat = Array.from({length: n+1}, (_, i) => 0); for (i = 1; i <= n; i++) dat[arr[i - 1]] = i; let b = Array.from({length: n+1}, (_, i) => 0); let j = 0, c; // Calculating steps required // for each element to reach // its sorted position for (i = 1; i <= n; i++) { c = 1; j = dat[i]; while (j != i) { c++; j = dat[j]; } b[i] = c; } // Calculate LCM of the array document.write(findlcm(b, n)); } // Driver Code let arr = [ 5, 1, 4, 3, 2, 7, 6 ]; let N = arr.length; minimumSteps(arr, N); </script> |
6
Time Complexity: O(NlogN)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!