R@M3\$H.NBlog

# [ARRAY] Relocate arr[I] = arr[arr[I]]

### 03 March, 2014 - 2 min read

WAP to modify the array such that arr[I] = arr[arr[I]].
Do this in place i.e. with out using additional memory.

example : if a = {2,3,1,0}
o/p = a = {1,0,3,2}

Note : The array contains 0 to n-1 integers.

void relocate(int *arr,int size) {
for(int i=0;i<size;i++) {
arr[i] += (arr[arr[i]]%size)*size;
}
for(int i=0;i<size;i++) {
arr[i] /= size;
}
}

It is simple maths:

(x + y*z)/z = y provided x and y is less than z.
(x + y*z)%z = x provided x and y is less than z.
This is the concept used here.
Example:
(3 + 4*5)/5 = 4
(3 + 4*5)%5 = 3

arr[i] = arr[i] + arr[arr[i]]*size
so arr[i]/size = arr[arr[i]]

In the code you see the author has used % below; this is done just to make sure arr[i] and arr[arr[i]] is less than size as explained earlier.
arr[i] += (arr[arr[i]]%size)*size;

When he multiplies the arr[arr[i]] by size and add the current value to it, you get a new value. This new value can use division to get the final result or modulo to obtain the current value.
When he does the division, the current value(remainder) just falls off and you get the final value.

In the first loop, I add (size * "OLD arr[arr[i]]") to arr[i] so that, when doing integer division by size, I get old arr[arr[i]], when doing %size, I get old arr[i]. However I add arr[arr[i]]%size to get old arr[arr[i]], in case it was already modified in the loop. The second loop simply replaces each arr[i] with old arr[arr[i]], as mentioned above.

FAQ:
Do we really need (arr[arr[i]] % size) why cant we directly put the arr[arr[i]] which i guess will yield the same result.since the values of array cannot be more than the size...
--- I think you need the %size because you can potentially retrieve the new final value from arr[arr[i]]. And that would mess up the calculation. You can try it with the input from the question:
{2,3,1,0} will become:
{1,0,3,6}