Monday, September 8, 2014

Get the maximum of A xor B where L<=A,B<=R

Loop over the bits from most significant to least significant of both L, and R. until you find a mismatch, assume the length of the mismatch from least significant is len then the answer = (1<<len)-1;

Why?
Assume this is our L, and R
R = xxxxx1yyyyyy
L = xxxxx0zzzzzz

then the 2 numbers would be
xxxxx1000000
xxxxx0111111

because
xxxxx0zzzzzz <= xxxxx0111111 <= xxxxx1yyyyyy
xxxxx0zzzzzz <= xxxxx1000000 <= xxxxx1yyyyyy

and the answer would be:
000001111111


Practice problem: http://codeforces.ru/contest/276/problem/D
Here is a nice solution (special thanks to OoO000oOOOoOooOo on Codeforces):



 ans=0;
 while(L!=R) { ans=ans*2+1; L>>=1; R>>=1; }
 cout << ans << endl;

No comments:

Post a Comment