We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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.
Xor-sequence
You are viewing a single comment's thread. Return to all 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