8. Rearrange an array so that arr[i] becomes arr[arr[i]]

with O(1) extra space

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.

Input: arr[]  = {3, 2, 0, 1}
Output: arr[] = {1, 0, 3, 2}
Explanation: 
In the given array 
arr[arr[0]] is 1 so arr[0] in output array is 1
arr[arr[1]] is 0 so arr[1] in output array is 0
arr[arr[2]] is 3 so arr[2] in output array is 3
arr[arr[3]] is 2 so arr[3] in output array is 2

Input: arr[] = {4, 0, 2, 1, 3}
Output: arr[] = {3, 4, 2, 0, 1}
Explanation:
arr[arr[0]] is 3 so arr[0] in output array is 3
arr[arr[1]] is 4 so arr[1] in output array is 4
arr[arr[2]] is 2 so arr[2] in output array is 2
arr[arr[3]] is 0 so arr[3] in output array is 0
arr[arr[4]] is 1 so arr[4] in output array is 1

Solution:

Approach: Increment every element at ith index is incremented by (arr[arr[i]] % n)*n Old value can be obtained by arr[i]%n and a new value can be obtained by arr[i]/n

class Solution
{
public:
    void rearrange(long long a[], int n)
    {

        for (int i = 0; i < n; i++)
        {
            a[i] += ((a[a[i]]) % n) * n;
        }

        for (int i = 0; i < n; i++)
        {
            a[i] = a[i] / n;
        }
    }
};

Time Complexity: O(n)