c++ – How to rearrange the elements of an array?

Question:

A sequence of numbers from 0 to N-1 ( N >= 2 – integer) was randomly shuffled, resulting in an array A of length N . It is necessary to modify the array so that at the end of the work, the new element A[i] contains the value equal to A[A[i]] in the old array, for all i from 0 to N-1 , using O(1) additional memory .

For example, on input A = {1, 2, 7, 0, 9, 3, 6, 8, 5, 4} .

Then the output A = {2, 7, 8, 1, 4, 0, 6, 5, 3, 9} .

I tried like this:

size_t pos_1 = 0, pos_2 = A[0], assigned = 0;

while (assigned != A.size() - 1 && pos_2 != 0) {
    std::swap(A[pos_1], A[pos_2]);
    std::swap(pos_1, pos_2);
    pos_2 = A[pos_2];
    ++assigned;
}

But, if we come again to the 0th element, and not everything has been exchanged yet, then the answer is wrong. Also tried the square solution:

size_t pos = 0, assigned = 0;
int tmp = A[A[pos]];

while (assigned != A.size()) {
    std::swap(A[pos], tmp);
    pos = std::find(A.cbegin(), A.cend(), pos) - A.cbegin();
    ++assigned;
}

But then at some stage there are 2 identical numbers in the array and std::find finds the first of them, which, generally speaking, is not true.

Answer:

In fact, this problem has a non-trivial, but very simple solution after delving into it 🙂

1. To each A[i] you need to add (A[A[i]]%N)*N
2. Each A[i] must be divided by N …

Everything!

int A[10] = {1, 2, 7, 0, 9, 3, 6, 8, 5, 4};

int main()
{
    for(int i = 0; i < 10; ++i)
        A[i] += (A[A[i]]%10)*10;

    for(int i = 0; i < 10; ++i)
        A[i] /= 10;

    for(int i = 0; i < 10; ++i)
        printf("%d  ",A[i]);

    puts("");
}