Rearrange the Array

Problem Statement

You are given a permutation array b[] of size n, containing every integer from 1 to n exactly once.

Initially:

Code

a = [1, 2, 3, ..., n]

During one operation:

The element at position i moves to position b[i].

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

Code

b = [1,2,3]

Initially:

Code

a = [1,2,3]

After one operation:

Code

a = [1,2,3]

Nothing changes because every element stays in its own position.

Answer

Code

Example 2

Input

Code

b = [2,3,1,5,4]

Initially:

Code

[1,2,3,4,5]

After each operation:

Code

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:

Code

b = [2,3,1,5,4]

contains two cycles.

Code

1 → 2 → 3 → 1

Cycle Length = 3

and

Code

4 → 5 → 4

Cycle Length = 2

A cycle returns to its original position after exactly its length number of operations.

Therefore:

First cycle returns after 3 operations.
Second cycle returns after 2 operations.

Both cycles become original together after:

Code

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

Code

visited[] = false

LCM = 1

For every index

    if not visited

         find cycle length

         LCM = LCM(LCM, cycleLength)

Return LCM

Java Code

Java

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

Java

class Solution {

This is the solution class required by GeeksforGeeks.

Mod Value

Java

static final int MOD = 1000000007;

Since the answer can become very large, we store it modulo 10⁹ + 7.

GCD Function

Java

private long gcd(long a, long b)

This function calculates the Greatest Common Divisor using the Euclidean Algorithm.

Example

Code

gcd(12,18)

18 % 12 = 6

12 % 6 = 0

Answer = 6

Code

Java

while(b!=0)

Continue until remainder becomes zero.

Java

long temp = a % b;

Store the remainder.

Java

a = b;
b = temp;

Shift values.

Finally:

Java

return a;

returns the GCD.

minOperations()

Java

int n = b.length;

Store array size.

Visited Array

Java

boolean[] vis = new boolean[n];

This prevents visiting the same cycle multiple times.

Initially:

Code

F F F F F

Initial LCM

Java

long lcm = 1;

Initially:

Code

LCM = 1

Traversing Every Node

Java

for(int i=0;i<n;i++)

Check every index.

New Cycle

Java

if(!vis[i])

If not already visited, start discovering one complete cycle.

Current Position

Java

int curr = i;

Suppose:

Code

i = 0

then:

Code

curr = 0

Cycle Length

Java

int len = 0;

Counts how many nodes are present in this cycle.

Traversing the Cycle

Java

while(!vis[curr])

Continue until we return to an already visited node.

Mark Visited

Java

vis[curr]=true;

Avoid revisiting.

Move to Next Position

Java

curr = b[curr]-1;

Why subtract one?

Input is:

Code

1 2 3 4

Java arrays use:

Code

0 1 2 3

Hence:

Code

-1

is required.

Increase Length

Java

len++;

Count one more element in this cycle.

Compute GCD

Java

long g = gcd(lcm,len);

Suppose:

Code

LCM = 6

Length = 8

Then:

Code

gcd(6,8)=2

Update LCM

Formula:

Code

LCM(a,b)

=

(a/GCD)*b

Code:

Java

lcm=(lcm/g)*len;

Example:

Code

LCM(6,8)

=(6/2)*8

=24

Apply Mod

Java

lcm%=MOD;

Keeps the answer within limits.

Return Answer

Java

return (int)lcm;

Dry Run

Input

Code

b=[2,3,1,5,4]

Visited:

Code

F F F F F

First Cycle

Code

1→2→3→1

Length:

Code

LCM:

Code

Visited:

Code

T T T F F

Second Cycle

Code

4→5→4

Length:

Code

LCM:

Code

LCM(3,2)

=6

Visited:

Code

T T T T T

Answer

Code

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)?

Every index is visited exactly once while discovering cycles.
GCD computation is efficient and negligible compared to the traversal.

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:

Code

LCM(a,b)= (a / gcd(a,b)) × b

Mark visited nodes to avoid processing the same cycle more than once.

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.