Minimum p[i] = p[arr[i]] operations to regain the given Array
Given an array, A[] (1 β indexed) of size βNβ which contains a permutation of [1, N], the task is to find the minimum number of operations to be applied on any array P[] to get back the original array P[]. The operation must be applied at least once. In each operation, for every index of P[] we set P[i] = P[A[i]].
Examples:
Input: A[] = {1, 3, 2}
Output: 2
Explanation: Let P[] = {7, 4, 2}.
After 1 operation, {P[1], P[3], P[2]} = {1, 2, 4}.
After 2 operations, {P[1], P[3], P[2]} = {7, 4, 2}
After 2 operation original array is reached.Input: A[] = {5, 4, 2, 3, 1}
Output: 6
Explanation: Let P = {1, 2, 3, 4, 5},
After 1 operation {P[5], P[4], P[2], P[3], P[1]} = {5, 4, 2, 3, 1}
After 2 operation {P[5], P[4], P[2], P[3], P[1]} = {1, 3, 4, 2, 5}
After 3 operation {P[5], P[4], P[2], P[3], P[1]} = {5, 2, 3, 4, 1}
After 4 operation {P[5], P[4], P[2], P[3], P[1]} = {1, 4, 2, 3, 5}
After 5 operation {P[5], P[4], P[2], P[3], P[1]} = {5, 3, 4, 2, 1}
After 6 operation {P[5], P[4], P[2], P[3], P[1]} = {1, 2, 3, 4, 5}
After 6 operation original array is reached.
Naive Approach:
A naive approach is to make any array and apply the given operation until the original array is reached again.
Below is the implementation of the approach.
C++
// C++ code for the naive approach #include <bits/stdc++.h> using namespace std; // comparing 2 arrays bool checkEqual(vector< int >& A, vector< int >& B) { for ( int i = 0; i < A.size(); i++) { if (A[i] != B[i]) return false ; } return true ; } // function to find minm operations int minOperations(vector< int >& A) { int N = A.size(); vector< int > P(N, 0); vector< int > originalArray(N, 0); // Let P be same as A for ( int i = 0; i < N; i++) { P[i] = A[i]; originalArray[i] = P[i]; } // after applying operation 1 time for ( int i = 0; i < N; i++) { P[i] = A[A[i] - 1]; } int operations = 1; while (!checkEqual(originalArray, P)) { vector< int > temp(N); for ( int i = 0; i < N; i++) { temp[i] = P[A[i] - 1]; } P = temp; operations++; } return operations; } int main() { // Given input vector< int > A = { 5, 4, 2, 3, 1 }; // Function call cout << minOperations(A); return 0; } // This code is contributed by rakeshsahni |
Java
// JAVA code for the naive approach import java.util.*; public class GFG { // comparing 2 arrays static boolean checkEqual( int [] A, int [] B) { for ( int i = 0 ; i < A.length; i++) { if (A[i] != B[i]) return false ; } return true ; } // function to find minm operations static int minOperations( int [] A) { int N = A.length; int [] P = new int [N]; int [] originalArray = new int [N]; // Let P be same as A for ( int i = 0 ; i < N; i++) { P[i] = A[i]; originalArray[i] = P[i]; } // after applying operation 1 time for ( int i = 0 ; i < N; i++) { P[i] = A[A[i] - 1 ]; } int operations = 1 ; while (!checkEqual(originalArray, P)) { int [] temp = new int [N]; for ( int i = 0 ; i < N; i++) { temp[i] = P[A[i] - 1 ]; } P = temp; operations++; } return operations; } public static void main(String[] args) { // Given input int [] A = { 5 , 4 , 2 , 3 , 1 }; // Function call System.out.println(minOperations(A)); } } |
Python3
# Python code for the above approach # comparing 2 arrays def checkEqual(A, B): for i in range ( len (A)): if (A[i] is not B[i]): return False return True # Function to find minimum operations def minOperations(A): N = len (A) P = [ 0 ] * N originalArray = [ 0 ] * N # let P be same as A for i in range (N): P[i] = A[i] originalArray[i] = P[i] # after applying operation 1 time for i in range (N): P[i] = A[A[i] - 1 ] operations = 1 while (checkEqual(originalArray, P) is not True ): temp = [ 0 ] * N for i in range (N): temp[i] = P[A[i] - 1 ] P = temp operations + = 1 return operations A = [ 5 , 4 , 2 , 3 , 1 ] # Function call print (minOperations(A)) # This code is contributed by lokesh. |
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { // comparing 2 arrays static bool checkEqual( int [] A, int [] B) { for ( int i = 0; i < A.Length; i++) { if (A[i] != B[i]) return false ; } return true ; } // function to find minm operations static int minOperations( int [] A) { int N = A.Length; int [] P = new int [N]; int [] originalArray = new int [N]; // Let P be same as A for ( int i = 0; i < N; i++) { P[i] = A[i]; originalArray[i] = P[i]; } // after applying operation 1 time for ( int i = 0; i < N; i++) { P[i] = A[A[i] - 1]; } int operations = 1; while (!checkEqual(originalArray, P)) { int [] temp = new int [N]; for ( int i = 0; i < N; i++) { temp[i] = P[A[i] - 1]; } P = temp; operations++; } return operations; } // Driver code public static void Main(String[] args) { // Given input int [] A = { 5, 4, 2, 3, 1 }; // Function call Console.WriteLine(minOperations(A)); } } // This code is contributed by code_hunt. |
Javascript
<script> // JS code to implement the approach // comparing 2 arrays function checkEqual(A, B) { for (let i = 0; i < A.length; i++) { if (A[i] != B[i]) return false ; } return true ; } // function to find minm operations function minOperations(A) { let N = A.length; let P = new Array(N); let originalArray = new Array(N); // Let P be same as A for (let i = 0; i < N; i++) { P[i] = A[i]; originalArray[i] = P[i]; } // after applying operation 1 time for (let i = 0; i < N; i++) { P[i] = A[A[i] - 1]; } let operations = 1; while (!checkEqual(originalArray, P)) { let temp = new Array(N); for (let i = 0; i < N; i++) { temp[i] = P[A[i] - 1]; } P = temp; operations++; } return operations; } // Driver code // Given input let A = [ 5, 4, 2, 3, 1 ]; // Function call document.write(minOperations(A)); // This code is contributed by sanjoy_62. </script> |
6
Time Complexity: O(N * minOperations), for executing the operations until the original array is retrieved.
Auxiliary Space: O(N), for creating an additional array of size P.
Efficient Approach:
Use the following idea to solve the problem:
It can be observed that the elements form a cycle. When all the cycles are completed at the same operation for the first time that many moves are required.
Each cycle is completed after making moves same as their length. So all the cycles are completed at the same operation for the first time when LCM(all cycle lengths) number of moves are made.
Follow the below steps to solve the problem:
- Declare an array βcycleLengths[]β to store the length of all cycles present.
- Declare a Boolean array βvisited[]β to check if the cycle length of corresponding element has already been calculated or not.
- For every unvisited index
- traverse all the elements of corresponding cycle while updating the βvisited[]β and store its length in βcycleLength[]β.
- Return the LCM of all numbers present in βcycleLength[]β.
Code implementation of above approach:
C++
// C++ code to implement the approach #include <iostream> #include <vector> using namespace std; // Function to calculate GCD of two numbers int gcd( int a, int b) { if (a == 0) return b; return gcd(b % a, a); } // Function to calculate LCM of two numbers int lcm( int a, int b) { return (a * b) / gcd(a, b); } // Traversing the cycle and returning // the length of the cycle int traverseCycle( int root, int A[], vector< int >& visited) { if (visited[root]) return 0; visited[root] = true ; return 1 + traverseCycle(A[root - 1], A, visited); } // Function to find minm operations int minOperations( int A[], int N) { vector< int > cycleLength; vector< int > visited(N + 1, 0); // Detecting all cycles and storing // their length in cycleLength List for ( int i = 1; i <= N; i++) { if (!visited[i]) { int len = traverseCycle(i, A, visited); cycleLength.push_back(len); } } // Finding lcm of all cycle lengths int res = 1; for ( auto cycleLen : cycleLength) { res = lcm(res, cycleLen); } return res; } // Driver code int main() { int A[] = { 5, 4, 2, 3, 1 }; // Function call cout << (minOperations(A, 5)) << endl; ; } // This code is contributed by garg28harsh |
Java
// Java code to implement the approach import java.util.*; public class GFG { // Function to calculate GCD of two numbers static int gcd( int a, int b) { if (a == 0 ) return b; return gcd(b % a, a); } // Function to calculate LCM of two numbers static int lcm( int a, int b) { return (a * b) / gcd(a, b); } // Traversing the cycle and returning // the length of the cycle static int traverseCycle( int root, int [] A, boolean [] visited) { if (visited[root]) return 0 ; visited[root] = true ; return 1 + traverseCycle(A[root - 1 ], A, visited); } // Function to find minm operations static int minOperations( int [] A) { int N = A.length; ArrayList<Integer> cycleLength = new ArrayList<>(); boolean [] visited = new boolean [N + 1 ]; // Detecting all cycles and storing // their length in cycleLength List for ( int i = 1 ; i <= N; i++) { if (!visited[i]) { int len = traverseCycle(i, A, visited); cycleLength.add(len); } } // Finding lcm of all cycle lengths int res = 1 ; for (Integer cycleLen : cycleLength) { res = lcm(res, cycleLen); } return res; } // Driver code public static void main(String[] args) { int [] A = { 5 , 4 , 2 , 3 , 1 }; // Function call System.out.println(minOperations(A)); } } |
Python3
class GFG: # Function to calculate GCD of two numbers @staticmethod def gcd(a, b): if (a = = 0 ): return b return GFG.gcd(b % a, a) # Function to calculate LCM of two numbers @staticmethod def lcm(a, b): return int ((a * b) / GFG.gcd(a, b)) # Traversing the cycle and returning # the length of the cycle @staticmethod def traverseCycle(root, A, visited): if (visited[root]): return 0 visited[root] = True return 1 + GFG.traverseCycle(A[root - 1 ], A, visited) # Function to find minm operations @staticmethod def minOperations(A): N = 5 cycleLength = [] visited = [ False ] * (N + 1 ) # Detecting all cycles and storing # their length in cycleLength List i = 1 while (i < = N): if ( not visited[i]): len = GFG.traverseCycle(i, A, visited) cycleLength.append( len ) i + = 1 # Finding lcm of all cycle lengths res = 1 for cycleLen in cycleLength: res = GFG.lcm(res, cycleLen) return res # Driver code @staticmethod def main(args): A = [ 5 , 4 , 2 , 3 , 1 ] # Function call print (GFG.minOperations(A)) if __name__ = = "__main__" : GFG.main([]) |
C#
// C# code to implement the approach using System; using System.Collections.Generic; public class GFG { // Function to calculate GCD of two numbers static int gcd( int a, int b) { if (a == 0) return b; return gcd(b % a, a); } // Function to calculate LCM of two numbers static int lcm( int a, int b) { return (a * b) / gcd(a, b); } // Traversing the cycle and returning // the length of the cycle static int traverseCycle( int root, int [] A, Boolean[] visited) { if (visited[root]) return 0; visited[root] = true ; return 1 + traverseCycle(A[root - 1], A, visited); } // Function to find minm operations static int minOperations( int [] A) { int N = A.Length; List< int > cycleLength = new List< int >(); Boolean[] visited = new Boolean[N + 1]; // Detecting all cycles and storing // their length in cycleLength List for ( int i = 1; i <= N; i++) { if (!visited[i]) { int len = traverseCycle(i, A, visited); cycleLength.Add(len); } } // Finding lcm of all cycle lengths int res = 1; foreach ( int cycleLen in cycleLength) { res = lcm(res, cycleLen); } return res; } // Driver code public static void Main() { int [] A = { 5, 4, 2, 3, 1 }; // Function call Console.Write(minOperations(A)); } } // This code is contributed by saurabh_jaiswal. |
Javascript
// Javascript code to implement the approach // Function to calculate GCD of two numbers function gcd(a, b) { if (a == 0) return b; return gcd(b % a, a); } // Function to calculate LCM of two numbers function lcm(a, b) { let c = a * b; return (c / gcd(a, b)); } // Traversing the cycle and returning // the length of the cycle function traverseCycle(root, A, visited) { if (visited[root]) return 0; visited[root] = true ; return 1 + traverseCycle(A[root - 1], A, visited); } // Function to find minm operations function minOperations(A, N) { let cycleLength = []; let visited = []; for (let i = 0; i <= N; i++) { visited.push(0); } // Detecting all cycles and storing // their length in cycleLength List for (let i = 1; i <= N; i++) { if (visited[i] == false ) { let len = traverseCycle(i, A, visited); cycleLength.push(len); } } // Finding lcm of all cycle lengths let res = 1; for (let i = 0; i < cycleLength.length; i++) { res = lcm(res, cycleLength[i]); } return res; } // Driver code let A = [ 5, 4, 2, 3, 1 ]; // Function call console.log(minOperations(A, 5)); // This code is contributed by garg28harsh. |
6
Time Complexity: O(N*log(Arr[i])), where N is the size of the given array.
Auxiliary Space: O(N), for creating an additional array of size N + 1.