My thought process about the magic formula of virtual indexing

  • 0

    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:
    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:

    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.

Log in to reply

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