You are not logged in. Please login at www.codechef.com to post your questions!

×

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

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

Expected Complexity: logN

asked 10 Sep '16, 12:36

saksham458's gravatar image

0★saksham458
4649
accept rate: 50%


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, & \text{n mod 4 = 0}\\ 1, & \text{n mod 4 = 1}\\ n+1, & \text{n mod 4 = 2}\\ 0, & \text{n mod 4 = 3} \end{array}\right\} $$

Time Complexity - $O(1)$

link

answered 10 Sep '16, 16:42

codechefwaale's gravatar image

3★codechefwaale
20
accept rate: 0%

@drcoderji

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

link

answered 10 Sep '16, 13:52

jaydeep97's gravatar image

5★jaydeep97
462
accept rate: 20%

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

link

answered 02 Oct '16, 16:28

smsubham's gravatar image

3★smsubham
675216
accept rate: 15%

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

link

answered 02 Oct '16, 19:52

ankesh18's gravatar image

6★ankesh18
627111
accept rate: 7%

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.

link

answered 23 Jul '17, 20:02

dark_stranger's gravatar image

2★dark_stranger
21
accept rate: 0%

@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.

(23 Jul '17, 22:38) arpit7281★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,167
×1,656
×1,404
×303

question asked: 10 Sep '16, 12:36

question was seen: 8,793 times

last updated: 23 Jul '17, 20:02