Simple and fast Java solution with explanation

• For this problem, the naive approach is to iterate from n to m and & all the values. However, this approach is time consuming because it waste time to & values which will eventually be 0. The insight of this problem is that we can be sure the value & from n to m will be 0 if the index of the highest 1 in n's binary representation is different from the index of the highest 1 in m's binary representation. For example if we have n=001 and m=110, we will have two value in between which could be 001 and 100 and these two & will be 0 which makes the whole value 0. Here goes my code in java, hope it will explain itself:

``````public class Solution {
public int rangeBitwiseAnd(int m, int n) {
int p1=0, p2=0;
int val1=m, val2=n;
while(val1>1 || val2>1)
{
if(val1>1)
{
val1=val1/2;
p1++;
}
if(val2>1)
{
val2=val2/2;
p2++;
}
}
if(p1!=p2) return 0;

int result=~0;
for(int i=m;i<n;i++)
result=result&i;
result=result&n;
return result;
}
}``````

• Thanks for the solution. The original code pass all cases.
Then I tried to replace the loop to

``````for(int i=m;i<=n;i++)
result=result&i;
``````

and remove

``````result=result&n;
``````

but got Time Limit Exceeded at test case:

Last executed input:
2147483646, 2147483647

Could anyone explain?
Thanks!

• This is because when n is 2147483647, n+1 will be 2147483648 which will ticks over to -2147483648. So I just make it a separate & operation after the for loop in case the i ticks over

• Thanks for the explanation!
When i=2147483647, i++ will become -2147483648 and it's <= 2147483647. The loop become infinite.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.