New update is available. Click here to update.

Rearrange Array

PROBLEM STATEMENT

You're given an array ARR[] of size N, where every element belongs to the range 0 to N-1. Your task is to rearrange the given array so that ARR[i] becomes ARR[ARR[i]] and make sure that this task is done with O(1) extra space.

Input Format :

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.

Output Format :

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

Note :

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

Constraints :

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

Approach 1

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.

Try Problem