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 minimumnon-zero number of operations you need to perform on _perm to return the permutation to its initial value.

Examples

Example 1

1
2
3
4
5

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

1
2
3
4
5
6

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

1
2

Input: n = 6
Output: 4

Constraints

  • 2 <= n <= 1000
  • n​​​​​​ is even.

Solution

Method 1 – Cycle Length Simulation

Intuition

The permutation returns to its initial state after a certain number of operations. Instead of simulating the whole array, we can track the position of one element (e.g., index 1) and count how many steps it takes to return to its original position.

Approach

  1. Start with position = 1.
  2. For each operation, update position according to the rules:
    • If position % 2 == 0: position = position / 2
    • Else: position = n / 2 + (position - 1) / 2
  3. Count steps until position returns to 1.
  4. The answer is the number of steps.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int reinitializePermutation(int n) {
        int pos = 1, steps = 0;
        do {
            if (pos % 2 == 0) pos /= 2;
            else pos = n / 2 + (pos - 1) / 2;
            steps++;
        } while (pos != 1);
        return steps;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func reinitializePermutation(n int) int {
    pos, steps := 1, 0
    for {
        if pos%2 == 0 {
            pos /= 2
        } else {
            pos = n/2 + (pos-1)/2
        }
        steps++
        if pos == 1 {
            break
        }
    }
    return steps
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int reinitializePermutation(int n) {
        int pos = 1, steps = 0;
        do {
            if (pos % 2 == 0) pos /= 2;
            else pos = n / 2 + (pos - 1) / 2;
            steps++;
        } while (pos != 1);
        return steps;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    fun reinitializePermutation(n: Int): Int {
        var pos = 1; var steps = 0
        do {
            pos = if (pos % 2 == 0) pos / 2 else n / 2 + (pos - 1) / 2
            steps++
        } while (pos != 1)
        return steps
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def reinitializePermutation(self, n: int) -> int:
        pos, steps = 1, 0
        while True:
            if pos % 2 == 0:
                pos //= 2
            else:
                pos = n // 2 + (pos - 1) // 2
            steps += 1
            if pos == 1:
                break
        return steps
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn reinitialize_permutation(n: i32) -> i32 {
        let mut pos = 1;
        let mut steps = 0;
        loop {
            if pos % 2 == 0 {
                pos /= 2;
            } else {
                pos = n / 2 + (pos - 1) / 2;
            }
            steps += 1;
            if pos == 1 { break; }
        }
        steps
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    reinitializePermutation(n: number): number {
        let pos = 1, steps = 0;
        do {
            if (pos % 2 === 0) pos = pos / 2;
            else pos = Math.floor(n / 2 + (pos - 1) / 2);
            steps++;
        } while (pos !== 1);
        return steps;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — In worst case, up to n steps.
  • 🧺 Space complexity: O(1) — constant extra space.