Rearrange an array so that arr[i] becomes arr[arr[i]] with O(1) extra space | GeeksforGeeks

Given an array arr[] of size n where every element is in range from 0 to n-1. Rearrange the given array so that arr[i] becomes arr[arr[i]]. This should be done with O(1) extra space.
Examples:

Input: arr[]  = {3, 2, 0, 1}  Output: arr[] = {1, 0, 3, 2}

1) Increase every array element arr[i] by (arr[arr[i]] % n)*n.
2) Divide every element by n.

Let us understand the above steps by an example array {3, 2, 0, 1}
In first step, every value is incremented by (arr[arr[i]] % n)*n
After first step array becomes {7, 2, 12, 9}. 
The important thing is, after the increment operation
of first step, every element holds both old values and new values. 
Old value can be obtained by arr[i]%n and new value can be obtained
by arr[i]/n.

In second step, all elements are updated to new or output values 
by doing arr[i] = arr[i]/n.
After second step, array becomes {1, 0, 3, 2}

void rearrange(int arr[], int n)

{

    // First step: Increase all values by (arr[arr[i]]%n)*n

    for (int i=0; i < n; i++)

        arr[i] += (arr[arr[i]]%n)*n;

    // Second Step: Divide all values by n

    for (int i=0; i<n; i++)

        arr[i] /= n;

}

arr[i] += (arr[arr[i]]%n)*n;

http://www.techiedelight.com/rearrange-array-such-that-array-index-is-set-to-i/

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}.

    public static void rearrange(int A[], int n)

    {

        // for each element A[i] increment value present at index

        // (A[i] % n) by i*n

        for (int i = 0; i < n; i++)

            A[A[i] % n] += i*n;

    

        // traverse the modified array and set A[i] = A[i]/n

        for (int i = 0; i < n; i++)

            A[i] = A[i] / n;

    }

I think there is no need of performing '%' (modulo) operation. Because all the elements in array are in the range of 0 to n-1.

for the case of 

Input: arr[] = {4, 0, 2, 1, 3} so n=5.

for 0th element a[0]=a[0]+(a[a[0]%n)*n
= 4+(a[4]%5)*5
= 4+(3%5)*5
= 19
now a[0]=19. this is going to be used in the calculation of a[1].
for 1st element
a[1] = a[1] + (a[a[1]%n)*n
= 0 + (a[0]%5)*5
= 0 + (19%5)*5 ....As u asked the need of % here
= 0 + 4*5 .....if u will not use % then a[1] will
= 20 .....become 19*5=95 and later you will
.....will not get a[1] /=n as your output in
.....2nd step. It will produce a[1]=95/5=19.

http://www.techiedelight.com/rearrange-array-such-that-array-index-is-set-to-i/

    public static void rearrange(int A[], int n)

    {

        // create an auxiliary array of same size as A[]

        int[] aux = new int[n];

 

        // for each element A[i], set the value i at index A[i]

        // in the auxiliary array

        for (int i = 0; i < n; i++)

            aux[A[i]] = i;

    

        // update original array with auxiliary array elements

        for (int i = 0; i < n; i++)

            A[i] = aux[i];

    }

Read full article from Rearrange an array so that arr[i] becomes arr[arr[i]] with O(1) extra space | GeeksforGeeks