Rearrange Array

Rearrange a given array so that Arr[i] becomes Arr[Arr[i]] with O(1) extra space.

Also, the following holds true:

• All elements in the array are in the range [0, N-1]
• N * N does not overflow for a signed integer

Approach : Add the number (arr[arr[i]]%n)*n to each arr[i].  This step lets the array cell holds both the old value and the new value. The old value can be extracted by arr[i]%n and the new value by arr[i]/n.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

#include <iostream> using namespace std; void rearrangeArray(int *arr, int n){ //This step lets the array cell holds both the old value and the new value //The old value can be extracted by arr[i]%n and the new value by arr[i]/n for(int i = 0; i < n; i++){ arr[i] = arr[i] + (arr[arr[i]] % n)*n; } for(int i = 0; i < n; i++ ){ arr[i] = arr[i] / n; } } int main() { int arr[] = {4, 0, 2, 1, 3}; int n = sizeof(arr)/ sizeof(arr[0]); rearrangeArray(arr, n); for(int i = 0; i < n; i++ ){ cout << arr[i] << " "; } return 0; }