Problem Statement
You are given a permutation array b[] of size n, containing every integer from 1 to n exactly once.
Initially:
a = [1, 2, 3, ..., n]
During one operation:
You must perform at least one operation and determine the minimum number of operations required for the array to return to its original arrangement.
Since the answer can be very large, return it modulo 10^9 + 7.
Example 1
Input
b = [1,2,3]
Initially:
a = [1,2,3]
After one operation:
a = [1,2,3]
Nothing changes because every element stays in its own position.
Answer
1
Example 2
Input
b = [2,3,1,5,4]
Initially:
[1,2,3,4,5]
After each operation:
1 -> [3,1,2,5,4]
2 -> [2,3,1,4,5]
3 -> [1,2,3,5,4]
4 -> [3,1,2,4,5]
5 -> [2,3,1,5,4]
6 -> [1,2,3,4,5]
The array becomes original after 6 operations.
Key Observation
Since b[] is a permutation, every element belongs to exactly one cycle.
For example:
b = [2,3,1,5,4]
contains two cycles.
1 → 2 → 3 → 1
Cycle Length = 3
and
4 → 5 → 4
Cycle Length = 2
A cycle returns to its original position after exactly its length number of operations.
Therefore:
Both cycles become original together after:
LCM(3,2)=6
This is the required answer.
Approach
Create a visited array.
Traverse every index.
If the index is not visited, find its cycle length.
Compute the LCM of all cycle lengths.
Return the LCM modulo 10^9+7.
Algorithm
visited[] = false
LCM = 1
For every index
if not visited
find cycle length
LCM = LCM(LCM, cycleLength)
Return LCM
Java Code
class Solution {
static final int MOD = 1000000007;
// Function to calculate GCD using Euclidean Algorithm
private long gcd(long a, long b) {
while (b != 0) {
long temp = a % b;
a = b;
b = temp;
}
return a;
}
int minOperations(int[] b) {
int n = b.length;
boolean[] vis = new boolean[n];
long lcm = 1;
for (int i = 0; i < n; i++) {
if (!vis[i]) {
int curr = i;
int len = 0;
// Traverse one complete cycle
while (!vis[curr]) {
vis[curr] = true;
curr = b[curr] - 1;
len++;
}
long g = gcd(lcm, len);
lcm = (lcm / g) * len;
lcm %= MOD;
}
}
return (int) lcm;
}
}
Code Explanation
Class Declaration
class Solution {
This is the solution class required by GeeksforGeeks.
Mod Value
static final int MOD = 1000000007;
Since the answer can become very large, we store it modulo 10⁹ + 7.
GCD Function
private long gcd(long a, long b)
This function calculates the Greatest Common Divisor using the Euclidean Algorithm.
Example
gcd(12,18)
18 % 12 = 6
12 % 6 = 0
Answer = 6
Code
while(b!=0)
Continue until remainder becomes zero.
long temp = a % b;
Store the remainder.
a = b;
b = temp;
Shift values.
Finally:
return a;
returns the GCD.
minOperations()
int n = b.length;
Store array size.
Visited Array
boolean[] vis = new boolean[n];
This prevents visiting the same cycle multiple times.
Initially:
F F F F F
Initial LCM
long lcm = 1;
Initially:
LCM = 1
Traversing Every Node
for(int i=0;i<n;i++)
Check every index.
New Cycle
if(!vis[i])
If not already visited, start discovering one complete cycle.
Current Position
int curr = i;
Suppose:
i = 0
then:
curr = 0
Cycle Length
int len = 0;
Counts how many nodes are present in this cycle.
Traversing the Cycle
while(!vis[curr])
Continue until we return to an already visited node.
Mark Visited
vis[curr]=true;
Avoid revisiting.
Move to Next Position
curr = b[curr]-1;
Why subtract one?
Input is:
1 2 3 4
Java arrays use:
0 1 2 3
Hence:
-1
is required.
Increase Length
len++;
Count one more element in this cycle.
Compute GCD
long g = gcd(lcm,len);
Suppose:
LCM = 6
Length = 8
Then:
gcd(6,8)=2
Update LCM
Formula:
LCM(a,b)
=
(a/GCD)*b
Code:
lcm=(lcm/g)*len;
Example:
LCM(6,8)
=(6/2)*8
=24
Apply Mod
lcm%=MOD;
Keeps the answer within limits.
Return Answer
return (int)lcm;
Dry Run
Input
b=[2,3,1,5,4]
Visited:
F F F F F
First Cycle
1→2→3→1
Length:
3
LCM:
1
↓
3
Visited:
T T T F F
Second Cycle
4→5→4
Length:
2
LCM:
LCM(3,2)
=6
Visited:
T T T T T
Answer
6
Correctness Proof
Every permutation can be decomposed into independent cycles.
A cycle of length k returns to its original state after exactly k operations.
All cycles must return simultaneously for the array to become original.
The smallest number divisible by all cycle lengths is their Least Common Multiple (LCM).
Therefore, the algorithm correctly computes the minimum number of operations required.
Complexity Analysis
| Complexity | Value |
|---|
| Time Complexity | O(n) |
| Space Complexity | O(n) |
Why O(n)?
Interview Tips
Recognize that a permutation naturally forms disjoint cycles.
Each cycle returns after its own length.
The overall answer is the LCM of all cycle lengths.
Use GCD to compute the LCM efficiently:
LCM(a,b)= (a / gcd(a,b)) × b
Key Takeaway
The problem is not about simulating the rearrangements. Instead, decompose the permutation into cycles, find each cycle's length, and compute the LCM of those lengths. This yields the minimum number of operations for the entire array to return to its original configuration.
Summary
A permutation can always be represented as a collection of disjoint cycles. Since each cycle returns to its original state after a number of operations equal to its length, the entire array returns to its original arrangement when all cycles complete simultaneously. Computing the Least Common Multiple (LCM) of all cycle lengths provides the minimum number of required operations. By traversing each cycle exactly once using a visited array, the solution achieves O(n) time complexity and O(n) space complexity.