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.
This approach involves simulating the operation directly. We initialize the permutation array and iteratively apply the operations until it becomes identical to the initial permutation. Each operation updates the permutation based on the rules provided, and a counter is incremented to track the number of operations performed.
This C solution initializes a permutation array and an auxiliary array. It simulates the permutation operation as described, updating the permutation until it returns to its initial configuration. The number of operations needed is counted and returned.
Time Complexity: O(n^2) due to the iteration and copying of arrays on each operation.
Space Complexity: O(n) for storing the arrays.
This approach leverages cycle detection in permutations. The problem can be seen as finding the number of steps needed for a specific permutation transformation (defined by the operations) to return to its initial order. By following positions in the permutation and spotting cycles, one can figure out the number of complete cycle operations needed directly.
This C solution employs a cycle detection algorithm where k is updated according to the transformation rules. The cycle completes when k returns to 1, signifying that the permutation is in its original state again. The number of iterations corresponds to the required operations.
Time Complexity: O(n) as the cycle length is typically less than n.
Space Complexity: O(1) as no extra storage is used except for a few variables.
| Approach | Complexity |
|---|---|
| Simulate the Permutation Process | Time Complexity: O(n^2) due to the iteration and copying of arrays on each operation. |
| Cycle Detection in Permutations | Time Complexity: O(n) as the cycle length is typically less than n. |
| 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. |
1806. Minimum Number of Operations to Reinitialize a Permutation (Leetcode Medium) • Programming Live with Larry • 877 views views
Watch 4 more video solutions →Practice Minimum Number of Operations to Reinitialize a Permutation with our built-in code editor and test cases.
Practice on FleetCode