Easy Java/C++ Solution(Using Recursion)


  • 0
    S

    Recursion Solution
    The intuition behind this solution is that for range Bitwise And of numbers between m and n (inclusive) is that their highest 1 bit should be same.
    For ex
    for 6(110) and 7(111) highest bit of both numbers are same (3rd bit).
    The reason behind this is that between m and n if there exists a power of 2 then for BitwiseAnd of range to be greater than zero all the numbers should have this bit true else BitwiseAnd will be zero.If all numbers lie between two powers of 2 then bitwiseAnd will further be calculated using recursion for remaining range.

    public int rangeBitwiseAnd(int m, int n) {
            if(m==0){return 0;}
            int x1=get(m); //Get highest bit of m
            int x2=get(n);//Get highest bit of n
            if(x1!=x2){return 0;} 
            int k=(1<<x1);
            return k+rangeBitwiseAnd(m%k,n%k);
        }
        public static int get(int m){
            int a=0;
            while(m>1){
                a++;m=m/2;
            }
            return a;
        }
    

Log in to reply
 

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