How to find XOR of all the elements in given range?

algorithm
data-structure
dynamic-programming
xor

#1

given to integers A and B A<=B find XOR of all the elements between them.

Expected Complexity: logN


#2

@drcoderji

No, it is not always true. If A=2, B=3, then your answer will be 5. But 2^3 = 1.


#3

Let us denote f(n) = 1 \oplus 2 \oplus 3 \oplus \dots \oplus n, where \oplus denotes XOR operation
then XOR of all numbers between A and B can be represented by f(B) \oplus f(A-1), because x \oplus x = 0

Now we can find out easily that,

f(n) = \left\{\begin{array}{@{}lr@{}} n, & ext{n mod 4 = 0}\\ 1, & ext{n mod 4 = 1}\\ n+1, & ext{n mod 4 = 2}\\ 0, & ext{n mod 4 = 3} \end{array}\right\}

Time Complexity - O(1)


#4

Similar question in stackoverflow. Hope it helps. happy coding.
link text


#5

@jaydeep97 -its right. The answer will be f(3)^f(1)=0^1=1.


#6

can anybody help me if the array is given and range is also given …
if array is 1 2 7 4 5
a=3 b=4 ans should be 3 but above solution gives 7 ans.


#7

@dark_stranger

in this question range means all the no. in that range. suppose a=3 b=7 then this means we have to find 3^4^5^6^7.