Minimum Number of Operations to Reinitialize a Permutation

Minimum Number of Operations to Reinitialize a Permutation - 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.

Input & Output

Example 1 — Small Even Number

$ Input: n = 2

› Output: 1

💡 Note: Initial: [0,1]. After 1 operation: [0,1] (back to original). Answer: 1 operation.

Example 2 — Medium Size

$ Input: n = 4

› Output: 2

💡 Note: Initial: [0,1,2,3]. After 1 op: [0,2,1,3]. After 2 ops: [0,1,2,3] (back to original). Answer: 2 operations.

Example 3 — Larger Size

$ Input: n = 6

› Output: 4

💡 Note: Initial: [0,1,2,3,4,5]. Takes 4 operations to return to this exact permutation.

Constraints

2 ≤ n ≤ 1000
n is even

Visualization

Tap to expand

Understanding the Visualization

Input

Even integer n representing permutation size

Process

Apply transformation repeatedly until back to original

Output

Minimum operations needed for full cycle

Key Takeaway

🎯 Key Insight: Track only one element's position - when it returns to start, the entire permutation has cycled

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that we only need to track one element's position through the permutation cycle. The optimal approach tracks element 1's position using the transformation formula until it returns to position 1. Time: O(k) where k is cycle length, Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(n × k)	O(n)	Simulate the permutation operation repeatedly until we get back to the original
Single Element Tracking	O(k)	O(1)	Track only one element's position instead of the entire array

Brute Force Simulation — Algorithm Steps

Step 1: Create initial permutation [0, 1, 2, ..., n-1]
Step 2: Apply transformation to create new array
Step 3: Compare with original, increment counter
Step 4: Repeat until arrays match

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Start with [0,1,2,3,4,5]

Apply Transform

Create new array using transformation rules

Compare & Repeat

Check if back to original, continue if not

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int n) {
    // Create initial permutation
    int* original = malloc(n * sizeof(int));
    int* perm = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        original[i] = i;
        perm[i] = i;
    }
    
    int operations = 0;
    
    while (1) {
        // Apply one operation
        int* arr = malloc(n * sizeof(int));
        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];
            }
        }
        
        free(perm);
        perm = arr;
        operations++;
        
        // Check if we're back to original
        if (memcmp(perm, original, n * sizeof(int)) == 0) {
            free(original);
            free(perm);
            return operations;
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × k)

k operations, each taking O(n) time to transform and compare arrays

✓ Linear Growth

Space Complexity

O(n)

Need to store the permutation array of size n

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~15 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler