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):
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