# Rearrange array such that A[A[i]] is set to i for every element A[i]

Given an unsorted array of integers whose each element lies in range 0 to n-1 where n is the size of the array, rearrange array such that A[A[i]] is set to i for every element A[i] in the array.

Do this in linear time and without using any extra constant space.

For example,

Input:  {1, 3, 4, 2, 0}
Output: {4, 0, 3, 1, 2}

Explanation:
A[0] = 1, A[1] becomes 0
A[1] = 3, A[3] becomes 1
A[2] = 4, A[4] becomes 2
A[3] = 2, A[2] becomes 3
A[4] = 0, A[0] becomes 4

Simple solution would be to create an auxiliary array of size n and for each element A[i] of the input array, we set value i at index A[i] in the auxiliary array.

Output:

4 0 3 1 2

Output:

4 0 3 1 2

## Java

Output:

4 0 3 1 2

The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

Above solution uses extra space that violates the problem constraints. We can solve this problem without using any extra space by taking advantage of the fact that array elements lies in the range 0 to n-1. For each element A[i] present in the array, we increment value present at index (A[i] % n) by i*n. Finally, we traverse the modified array and set (A[i] = A[i]/n).

For example, consider array {1, 3, 4, 2, 0}. After incrementing value present at index (A[i] % n) for each element A[i] by i*n, the array becomes

{1 + 5*4, 3, 4 + 5*3, 2 + 5*1, 0 + 5*2} = {21, 3, 19, 7, 10}.

Now if we take (arr[i]/n) for each index i, we get {4, 0, 3, 1, 2}.

Output:

4 0 3 1 2

Output:

4 0 3 1 2

## Java

Output:

4 0 3 1 2

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).