Rearrange Array

Given an array, rearrange the values so that array[i] = array[arr[i]] without using any temporary storage. You can assume each value is smaller than the size of the array.

Example,
Input: {2, 3, 1, 0}
Output: {1, 0, 3, 2}
// The approach is to temporarily save two values in one slot. We can do this
// because we can assume each value is no bigger than the size of the array;
// therefore, value A can be saved as (value * size) and value B can be 
// just added to it. This will allow us to retrieve value A by executing
// (array[i] / size), and value B by (array[i] % size). 
void RearrangeArray(vector<int> &arr)
{
    // Add secnd value as multiplication of the value and the array size,
    // but perform a mod before reading the value in case this operation
    // was already performed on that slot.
    for (int i = 0; i < arr.size(); i++)
        arr[i] += (arr[arr[i]] % arr.size()) * arr.size();
    // Now all values are placed in the right location. Get rid of the
    // values temporarily stored as size multiplications.
    for (int i = 0; i < arr.size(); i++)
        arr[i] /= arr.size();
}
Comments