# Minimum Number of Operations to Reinitialize a Permutation
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-number-of-operations-to-reinitialize-a-permutation)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-operations-to-reinitialize-a-permutation
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array
---
## Problem
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`:

* If `i % 2 == 0`, then `arr[i] = perm[i / 2]`.
* If `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 <= 1000`
* `n`​​​​​​ is even.

# Approaches
## Direct Simulation
This approach directly simulates the process described in the problem. We start with the initial permutation `perm = [0, 1, ..., n-1]` and repeatedly apply the given transformation rule. We keep a count of the operations. After each operation, we check if the current permutation has returned to its initial state. The simulation stops when the permutation is reinitialized, and we return the operation count.
**Time:** O(k * n), where `k` is the number of operations required. In each step, we iterate through the array of size `n` to build the new permutation and another O(n) to compare. The number of operations `k` can be at most `n`. Thus, the worst-case time complexity is O(n^2). · **Space:** O(n). We need to store the initial permutation, the current permutation, and the temporary array for the next permutation, each of size `n`.
**Pros:** Simple to understand and implement as it directly models the problem statement.; Guaranteed to find the correct answer.
**Cons:** Inefficient for larger values of `n` due to repeated array creation and comparison.; Higher space complexity compared to more optimized approaches.
### Explanation
The most straightforward way to solve the problem is to perform the simulation exactly as stated. We maintain the current state of the permutation, `perm`, and compare it against its initial state after each operation. 

We begin by creating two arrays: `initial` to hold the starting permutation `[0, 1, ..., n-1]` for reference, and `perm` which will be transformed. We then enter a loop. In each iteration, we count it as one operation, create a new array `arr` based on the transformation rules applied to `perm`, and then update `perm` with the contents of `arr`. We then check if `perm` is equal to `initial`. Since we are looking for a non-zero number of operations, this process is guaranteed to execute at least once. The loop terminates when `perm` is reinitialized, and we return the total count of operations.

```java
import java.util.Arrays;

class Solution {
    public int reinitializePermutation(int n) {
        int[] initial = new int[n];
        int[] perm = new int[n];
        for (int i = 0; i < n; i++) {
            initial[i] = i;
            perm[i] = i;
        }

        int ops = 0;
        // We need at least one operation, so a do-while loop is suitable.
        do {
            ops++;
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                if (i % 2 == 0) {
                    arr[i] = perm[i / 2];
                } else {
                    arr[i] = perm[n / 2 + (i - 1) / 2];
                }
            }
            // Assign the new permutation to perm
            perm = arr;
        } while (!Arrays.equals(perm, initial));
        
        return ops;
    }
}
```
### Algorithm
1. Store the initial permutation `[0, 1, ..., n-1]` in a reference array, say `initial`.
2. Create a working permutation array, `perm`, also initialized to `[0, 1, ..., n-1]`.
3. Initialize an operation counter, `ops`, to 0.
4. Start a `do-while` loop or a `while(true)` loop.
5. Inside the loop, increment `ops`.
6. Create a new temporary array, `arr`, of size `n`.
7. Populate `arr` based on the current `perm` using the rules:
   - `arr[i] = perm[i / 2]` for even `i`.
   - `arr[i] = perm[n / 2 + (i - 1) / 2]` for odd `i`.
8. Update `perm` to be equal to `arr`.
9. The loop continues until the current `perm` becomes identical to the `initial` array.
10. After the loop terminates, return `ops`.

## Mathematical Approach by Tracking a Single Element
A more efficient approach comes from analyzing the movement of indices. We can observe that the indices `0` and `n-1` are fixed points in this permutation. For any other index, its new position after one operation can be described by a mathematical formula. The number of operations to return the entire permutation to its initial state is the same as the number of operations for any single element (like element `1`) to return to its original position. This is because the permutation operation is applied uniformly to all indices, and the order of the permutation is determined by the length of the cycle containing these indices.
**Time:** O(k), where `k` is the result. The loop runs exactly `k` times. Since `k` is the order of the permutation, `k` is at most `n`. Therefore, the time complexity is O(n). · **Space:** O(1). We only use a few variables to keep track of the current position and the operation count.
**Pros:** Highly efficient with O(n) time complexity.; Constant space complexity, O(1), as it avoids creating and manipulating large arrays.
**Cons:** Requires a mathematical insight into the permutation's structure, which is less obvious than direct simulation.
### Explanation
Instead of simulating the entire permutation, we can track the position of a single element. The elements at index `0` and `n-1` always stay in place. Let's track the position of the element that starts at index `1`.

The position of an element at index `j` moves to a new index `i` based on the inverse of the given rules. The new position `i` is `2*j` if `j < n/2` and `2*j - n + 1` if `j >= n/2`. 

We can start with `pos = 1`. After one operation, the element at `1` moves to `pos = 2*1 = 2`. We can then repeatedly apply this transformation to the current position and count the operations until the position returns to `1`. The number of operations required for this single element to complete its cycle is the answer for the entire permutation. This is because the permutation forms cycles, and the answer is the least common multiple (LCM) of the cycle lengths. It turns out that for this specific permutation, all relevant indices belong to cycles whose lengths divide the length of the cycle containing `1`.

This reduces the problem from an O(n) operation per step to an O(1) operation per step.

```java
class Solution {
    public int reinitializePermutation(int n) {
        // For n=2, perm=[0,1] -> [0,1] in 1 op.
        if (n == 2) {
            return 1;
        }

        // We track the position of the element initially at index 1.
        // After 1 operation, the element at index 1 moves to index 2.
        int ops = 1;
        int pos = 2;

        // We continue until the element returns to index 1.
        while (pos != 1) {
            ops++;
            // Apply the position transformation rule
            if (pos < n / 2) {
                pos = 2 * pos;
            } else {
                pos = 2 * pos - (n - 1); // This is equivalent to 2*pos - n + 1
            }
        }

        return ops;
    }
}
```
### Algorithm
1. Observe that indices `0` and `n-1` are fixed points and do not change their values.
2. Analyze the movement of any other index, for example, index `1`.
3. After one operation, the value at index `1` moves to a new position. Let's track this position.
4. Start with `pos = 1` (the initial position of value `1`). After the first operation, its new position will be `2 * 1 = 2`.
5. Initialize an operation counter `ops = 1` and the current position `pos = 2`.
6. Start a loop that continues as long as `pos` is not back to `1`.
7. Inside the loop, update the position `pos` using the transformation rule:
   - If `pos < n / 2`, `pos = 2 * pos`.
   - If `pos >= n / 2`, `pos = 2 * pos - n + 1`.
8. Increment `ops` in each iteration.
9. When `pos` becomes `1`, the loop terminates. Return `ops`.

# Solutions
### Java

```java
class Solution {
public
  int reinitializePermutation(int n) {
    int ans = 0;
    for (int i = 1;;) {
      ++ans;
      if (i < (n >> 1)) {
        i <<= 1;
      } else {
        i = (i - (n >> 1)) << 1 | 1;
      }
      if (i == 1) {
        return ans;
      }
    }
  }
}

```

### Python

```python
class Solution:
    def reinitializePermutation(self, n: int) -> int: ans, i = 0, 1 while 1: ans += 1 if i < n >> 1: i <<= 1 else: i = (i - (n >> 1)) << 1 | 1 if i == 1: return ans

```

### CPP

```cpp
class Solution {
public:
  int reinitializePermutation(int n) {
    int ans = 0;
    for (int i = 1;;) {
      ++ans;
      if (i < (n >> 1)) {
        i <<= 1;
      } else {
        i = (i - (n >> 1)) << 1 | 1;
      }
      if (i == 1) {
        return ans;
      }
    }
  }
};

```