## 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 🙂

- To each
`A[i]`

you need to add`(A[A[i]]%N)*N`

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