2 approach | CPP | JAVA | PYTHON CODE- beginner to advanced
IntuitionWe are given an arraypermof size n where perm[i] = i. The goal is to find the minimum number of operations required to restore perm to its original ord
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
We are given an array` perm `of size `n` where `perm[i] = i`. The goal is to find the minimum number of operations required to restore perm to its original order after repeatedly applying a specific transformation:

- If `i` is `even`, then `new_perm[i] = perm[i / 2]`
- If `i` is `odd`, then `new_perm[i] = perm[n / 2 + (i - 1) / 2]`

By analyzing the transformation pattern, we observe that each element follows a cycle. The key insight is to track the position of 1 because once 1 returns to index 1, the entire array is restored.

# Approach
<!-- Describe your approach to solving the problem. -->
1. Initialize pos = 1, which tracks the position of 1 in the array.
2. Apply transformations until pos returns to 1:
    - If pos is even, update it as pos = pos / 2.
    - If pos is odd, update it as pos = n / 2 + (pos - 1) / 2.
3. Count the number of operations required for pos to return to 1.

🔹 **Key Observation:** Instead of simulating the entire array, we only track pos, making the solution O(log n) efficient.



# Complexity
- Time complexity:$$O(log n) → $$Each operation reduces the problem size
<!-- Add your time complexity here, e.g.  -->

- Space complexity:$$O(1) → $$Only a few integer variables are used.
<!-- Add your space complexity here, e.g.  -->

# Code
```c++ []
class Solution {
public:
    int reinitializePermutation(int n) {
        int pos = 1, cnt = 0;
        do {
            if (pos % 2 == 0) pos /= 2;
            else pos = n / 2 + (pos - 1) / 2;
            cnt++;
        } while (pos != 1);
        return cnt;
    }
};

```
```java []
class Solution {
    public int reinitializePermutation(int n) {
        int pos = 1, cnt = 0;
        do {
            pos = (pos % 2 == 0) ? pos / 2 : n / 2 + (pos - 1) / 2;
            cnt++;
        } while (pos != 1);
        return cnt;
    }
}

```
```py []
class Solution:
    def reinitializePermutation(self, n: int) -> int:
        pos, cnt = 1, 0
        while True:
            if pos % 2 == 0:
                pos //= 2
            else:
                pos = n // 2 + (pos - 1) // 2
            cnt += 1
            if pos == 1:
                return cnt

```

---

### another approach 
```cpp []
class Solution {
public:
    bool check(vector<int> vec){
        for(int i=0;i<vec.size();i++){
            if(i!=vec[i])return false;
        }
        return true;
    }
    void operation(vector<int>& vec){
        vector<int> newvec(vec.size());
        for(int i=0;i<vec.size();i++){
            if(i%2==0)newvec[i]=vec[i/2];
            else newvec[i]=vec[vec.size() / 2 + (i - 1) / 2];
        }
        vec=newvec;
    }
    int reinitializePermutation(int n) {
        if (n == 2) return 1; 
        int cnt=1;
        vector<int> vec(n);
        std::iota(vec.begin(), vec.end(), 0);
        operation(vec);
        while(!check(vec)){
            cnt++;
            operation (vec);
        }
        return cnt;
    }
};
```


['Array', 'Math', 'Simulation', 'C++', 'Java', 'Python3']