Rearrange Array

Easy
0/40
Average time to solve is 15m
13 upvotes
Asked in companies
OYOFacebookMicrosoft

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
1
4
0 1 2 3
Sample Output 1:
0 1 2 3
Explanation of Sample Input 1 :
We can see that ARR[ARR[0]] i.e ARR[0] is 0, hence ARR[0] in the output array will be 0. Also, ARR[ARR[1]] i.e ARR[1]  is1, hence ARR[1] in the output array will be 1. Similarly,  ARR[ARR[2]] i.e ARR[2] is 2, hence ARR[2] in the output array will be 2. Finally, ARR[ARR[3]] i.e ARR[3] is 3, hence ARR[3] in the output array will be 3.
Sample Input 2 :
1
4
3 2 0 1
Sample Output 2 :
1 0 3 2
Explanation of Sample Input 2 :
We can see that ARR[ARR[0]] i.e ARR[3] is 1, hence ARR[0] in the output array will be 1. Also, ARR[ARR[1]] i.e ARR[2] is 0, hence ARR[1] in the output array will be 0. Similarly,  ARR[ARR[2]] i.e ARR[0] is 3, hence ARR[2] in the output array will be 3. Finally, ARR[ARR[3]] i.e ARR[1] is 2, hence ARR[3] in the output array will be 2.
Hint

Can you extract more than one entry from the given numbers?

Approaches (1)
Mathematics based approach

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.
Time Complexity

O(N), where N is the size of the array.

 

Since only one traversal of array is needed.

Space Complexity

O(1).

 

As we are using extra constant memory.

Code Solution
(100% EXP penalty)
Rearrange Array
Full screen
Console