Rearrange the Array

Problem Overview

Array b is a 1-based permutation: each operation replaces every position i with b[i].

Intuition

Array b is a 1-based permutation: each operation replaces every position i with b[i]. Applying the map repeatedly walks disjoint cycles. The configuration returns to the start exactly when every cycle has completed an integer number of laps — that first common time is the LCM of all cycle lengths (taken modulo 10^9+7 for large answers).

Algorithm

1Walk each unvisited index as a cycle: follow cur → b[cur]−1 until you loop, recording the cycle length.
2For each cycle length, factorize it and keep the maximum exponent of every prime across all cycles (this builds LCM).
3Multiply primes raised to those max exponents into the answer, taking mod 10^9+7 after each multiply.
4Return the modular LCM.

Example Walkthrough

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

1. Cycle 1→2→3→1 has length 3; cycle 4→5→4 has length 2.
2. LCM(3, 2) = 6.
3. After 6 operations every element is back to its original place.

Output: 6

Common Pitfalls

• Indices in b are 1-based — convert with b[cur] − 1.
• Do not compute LCM as (a*b)/gcd under a modulus; use prime-exponent max instead.
• Include length-1 cycles (fixed points); LCM with 1 does not change the answer.
• Use long for the running product before casting back to int.

Rearrange the Array.java

Java

// Approach: b is a 1-based permutation. Find all cycle lengths; answer is LCM of those
// lengths. Compute LCM via max prime exponents across cycle lengths, multiply out mod 1e9+7.
// Time: O(n √n) Space: O(n)

class Solution {

    static final int MOD = 1000000007;

    int minOperations(int[] b) {
        int n = b.length;
        boolean[] vis = new boolean[n];
        int[] maxPow = new int[n + 1];

        // Find cycle lengths
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                int len = 0;
                int cur = i;
                while (!vis[cur]) {
                    vis[cur] = true;
                    cur = b[cur] - 1; // 1-based to 0-based
                    len++;
                }

                // Prime factorization of cycle length
                int x = len;
                for (int p = 2; p * p <= x; p++) {
                    if (x % p == 0) {
                        int cnt = 0;
                        while (x % p == 0) {
                            x /= p;
                            cnt++;
                        }
                        maxPow[p] = Math.max(maxPow[p], cnt);
                    }
                }
                if (x > 1) {
                    maxPow[x] = Math.max(maxPow[x], 1);
                }
            }
        }

        long ans = 1;

        // Reconstruct LCM modulo MOD
        for (int p = 2; p <= n; p++) {
            for (int i = 0; i < maxPow[p]; i++) {
                ans = (ans * p) % MOD;
            }
        }

        return (int) ans;
    }
};

Was this solution helpful?