Simple and fast Java solution with explanation


  • 3
    L

    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;
        }
    }

  • 0
    Y

    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!


  • 0
    L

    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


  • 0
    Y

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


Log in to reply
 

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