Watch 5 video solutions for Minimum Number of Operations to Reinitialize a Permutation, a medium level problem involving Array, Math, Simulation. This walkthrough by Programming Live with Larry has 877 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an even integer n. You initially have a permutation perm of size n where perm[i] == i (0-indexed).
In one operation, you will create a new array arr, and for each i:
i % 2 == 0, then arr[i] = perm[i / 2].i % 2 == 1, then arr[i] = perm[n / 2 + (i - 1) / 2].You will then assign arr to perm.
Return the minimum non-zero number of operations you need to perform on perm to return the permutation to its initial value.
Example 1:
Input: n = 2 Output: 1 Explanation: perm = [0,1] initially. After the 1st operation, perm = [0,1] So it takes only 1 operation.
Example 2:
Input: n = 4 Output: 2 Explanation: perm = [0,1,2,3] initially. After the 1st operation, perm = [0,2,1,3] After the 2nd operation, perm = [0,1,2,3] So it takes only 2 operations.
Example 3:
Input: n = 6 Output: 4
Constraints:
2 <= n <= 1000n is even.Problem Overview: You start with a permutation perm = [0,1,2,...,n-1]. A specific shuffle rule generates a new permutation on each operation. The task is to determine how many operations are required until the permutation returns to its original state.
Approach 1: Simulate the Permutation Process (Time: O(n * k), Space: O(n))
The most direct method is to simulate the shuffle exactly as defined. For each operation, create a new array and compute each position based on the rule: if i is even, take perm[i/2]; if i is odd, take perm[n/2 + (i-1)/2]. Repeat the process until the permutation becomes [0,1,2,...,n-1] again. This approach mirrors the problem statement and is useful for understanding how the transformation behaves. Each step processes the entire array, so the cost per operation is O(n). The number of operations k depends on the cycle length of the permutation.
Approach 2: Cycle Detection in Permutations (Time: O(k) ≤ O(n), Space: O(1))
The shuffle is a deterministic permutation mapping. Instead of tracking the entire array, you only need to follow where a single index moves after each operation. Index 1 works well because 0 always stays fixed. Apply the same transformation rule to the index itself: if the position is even, it becomes pos/2; otherwise it becomes n/2 + (pos-1)/2. Continue updating the position until it returns to 1. The number of steps taken equals the cycle length of the permutation, which is the answer. This reduces the problem to simple arithmetic and avoids rebuilding arrays.
The insight is that the entire permutation returns to its original configuration once every element completes its cycle. Because all elements follow the same transformation structure, tracking a single representative index reveals the full cycle length.
Recommended for interviews: The cycle detection approach is what interviewers expect. Simulating the array shows you understand the transformation, but recognizing that the operation forms a permutation cycle demonstrates stronger understanding of math and permutation properties. The optimal solution also avoids unnecessary memory compared to brute-force simulation with arrays and works cleanly with simple array index arithmetic.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulate the Permutation Process | O(n * k) | O(n) | Best for understanding the transformation or verifying logic with direct simulation. |
| Cycle Detection in Permutations | O(k) ≤ O(n) | O(1) | Preferred solution in interviews and production due to constant space and simple index math. |