# 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, 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.

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 = {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("");
}
``````
Scroll to Top