I_am_THE_Duck's blog

By I_am_THE_Duck, history, 6 months ago, In English,

Given two integers $$$A$$$ and $$$B$$$, find $$$A$$$ $$$\oplus$$$ $$$($$$ $$$A$$$ $$$+$$$ $$$1$$$ $$$)$$$ $$$\oplus$$$ $$$($$$ $$$A$$$ $$$+$$$ $$$2$$$ $$$)$$$ $$$\oplus$$$ $$$\dots$$$ $$$\oplus$$$ $$$B$$$ where $$$A$$$ $$$<=$$$ $$$B$$$

No, not in linear time

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
6 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

You can use a trick, that 1 xor 2 xor .. xor (4 * x — 1) = 0.

And A xor A + 1 xor .. xor B = (1 xor 2 xor .. xor (A — 1)) xor (1 xor 2 .. xor B)

»
6 months ago, # |
Rev. 3   Vote: I like it -13 Vote: I do not like it

Let's make an array x , where x[0] = a[0] and x[i] = x[i-1]^a[i]; Now xor of l to r will be x[r]^x[l-1];

Now to do it in O(1) time you can do this -

int val = r%4;
if(val==0)
      return r;
else if(val==1)
      return 0;
else if (val==2)
      return n+1;
else return 0;
»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

The XOR sum of numbers from 1 to m equals:

m   if m%4 is 0
1   if m%4 is 1
m+1 if m%4 is 2
0   if m%4 is 3