Rearrange an array with O(1) extra space

 Rearrange an array with O(1) extra space

MediumAccuracy: 56.34%Submissions: 76K+Points: 4

Given an array arr[] of size N where every element is in the range from 0 to n-1. Rearrange the given array so that arr[i] becomes arr[arr[i]].

 

Example 1:

Input:
N = 2
arr[] = {1,0}
Output: 0 1
Explanation: 
arr[arr[0]] = arr[1] = 0.
arr[arr[1]] = arr[0] = 1.

 

Example 2:

Input:
N = 5
arr[] = {4,0,2,1,3}
Output: 3 4 2 0 1
Explanation: 
arr[arr[0]] = arr[4] = 3.
arr[arr[1]] = arr[0] = 4.
and so on.

 

Your Task:
You don't need to read input or print anything. The task is to complete the function arrange() which takes arr and N as input parameters and rearranges the elements in the array in-place. 

 

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

 

Constraints:
1 <= N <= 107
0 <= Arr[i] < N

 

Solution :
In this question we are asked to move the elements of the array such that the position of elements would be equal to the value of element currently and the value to be updated would be the value of the current index(value). 

Explanation: 

arr[] = {4,0,2,1,3}

arr[arr[0]] = arr[4] = 3.

So what we can do is :
make a new array where we store the values according to this logic and finally copy all the elements from the new array to this array.

void arrange(long long arr[],int n){

    long long new_arr[n];

    int temp=0;

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

        new_arr[i]=0;

    }

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

        temp=arr[i];        

        new_arr[i]=arr[temp];  

    }

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

        arr[i]=new_arr[i];

       }

}

Another approach :

We could also solve this by using some mathematics :

our good old formula :

                            dividend = divisor * quotient + remainder

we can use this formula to store two values at one index, and get whichever value we need by division (/) or remainder (%).