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(); } |