New update is available. Click here to update.

Last Updated: 15 Jan, 2021

Difficulty: Easy

```
The first line contains an integer 'T', denoting the number of test cases. The 'T' test cases follow.
The first line of each test case contains an integer N, the size of the array.
The second line of each test case contains N space-separated integers.
```

```
For each test case, print the rearranged array as described in the problem statement.
```

```
You don’t need to print anything, it has already been taken care of. Just implement the given function.
```

```
1 <= T <= 10^2
1 <= N <= 10^4
0 <= ARR[i] <= N-1
Where 'ARR[i]' is 'ith' element of ARR.
Time Limit : 1 sec
```

As we are not allowed to use any extra space, we need to find an array element that can store two values at the same time. To do so, we increment every element at the ith index by (arr[arr[i]]%N)*N. Now after this increment every element is now holding two values, the old value and the new value. The old value can be obtained by arr[i]%N and the new value can be obtained by arr[i]/N. Let us understand how this is achieved.

- Suppose you have two elements X and Y that are present in the given array.
- Since the array elements are less than N, both X and Y will also be less than N.
- So now if we increment X by Y*N, the element then becomes X+Y*N. Now if we perform the operation (X+Y*N)%N, we get X and when we perform the operation (X+Y*N)/N, we get Y.
- Example: X=4, Y=3, N=5
- X+Y*N = 4 + 3*5 = 19
- Now, 19%5 = 4(which is X) and 19/5 = 3(which is Y).

Now let’s see how to reach the solution to our problem.

- We will start by traversing the array from start to end.
- At every index i, we increment the current element by (arr[arr[i]]%N)*N.
- Now traverse the array again from start to end.
- Now since we need the new value for every index i, we divide the ith element by n i.e arr[i]/n and then print this element.

SIMILAR PROBLEMS

Missing Number

Posted: 30 Oct, 2022

Difficulty: Easy

Longest Subarray With Zero Sum

Posted: 3 Nov, 2022

Difficulty: Moderate

Merge Two Sorted Arrays Without Extra Space

Posted: 19 Nov, 2022

Difficulty: Moderate

Ninja And The Strictly Increasing Array

Posted: 27 Nov, 2022

Difficulty: Moderate

Negative To The End

Posted: 16 Dec, 2022

Difficulty: Easy

Popular Interview Problems: