Xor-sequence

  • + 0 comments

    i⊕1⊕(i+2)⊕0 is not the same as i⊕1⊕i⊕2⊕0 = 2, so I don't think the method mentioned in the previous post would work. Though, using the same idea of grouping, I grouped consecutive elements to simplify the result. For any i>0, Ai⊕Ai+1 = Ai⊕Ai⊕i+1 = i+1. So I was able to reduce the number of XOR operations by half to handle L, R <= 10^5.

    Case 1: (R-L) is odd

    AL⊕AL+1⊕...⊕AR-1⊕AR = (L+1)⊕(L+3)⊕...⊕(R-2)⊕R

    Case 2: (R-L) is even

    AL⊕AL+1⊕...⊕AR-1⊕AR = (L+1)⊕(L+3)⊕...⊕(R-1)⊕AR