# My thought process about the magic formula of virtual indexing

• I guess some guys share the same confusion about the magic formula (2*i+1)%(n|1) in the brilliant solution by @StefanPochmann
Hereby I would like to share my thought process about how to prove the correctness of this formula.

To begin with, let's start from a simple example:

``````Given index 0,1,...,8, we would like to have rewired indices as below:
[1,3,5,7,0,2,4,6,8]
On the magic formula, look at the first part 2*i+1:
it means for i and i+1, A(i+1) = A(i) + 2 when A(i+1) < n.
Hence we will start from 1,3,5,...
If n is odd, 1,3,5,... will end up with n%n = 0
then the sequence will become 1,3,5,...,n-2,0,2,4,...
Note that upper bound of i is n-1, hence the sequence will end with:
(2*(n-1)+1)%n equivalent to 2*(n-1) + 1 - n  = n-1
For now we can see how this magic formula works if n is odd. The mapped sequence of indices will be:
[1,3,5,...,n-2,0,2,4,...,n-1]
``````

After the discussion on n is odd, we can easily discuss the situation when n is even:

``````If we still mod n instead of n+1, of course we still start from 1,3,5,...
But notice that to make the formula work, the mapped sequence will reach n-2, which is even;
then turn to 0,2,4,...,n-1, where n-1 is odd.
Hence we definitely need to alter n to n+1.
``````

Hope this post may help someone.
Thanks much for this brilliant solution.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.