C++ 36ms recursive solution


  • 0
    T

    Idea: recursively locate the leftmost positions where all numbers in range has 1.

    Two observations:

    • If m == 0, result must be 0
    • If the largest power of 2 of m and n are not equal, return 0. Eg.,
      m = 0 0 1 x x x x
      n = 1 x x x x x x
      Then there must exists a number p in the sequence where:
      p = 1 0 0 0 0 0 0
      Thus, result must be 0.

    Recursively locate the leftmost 1, add the power of 2 to result, subtract this number from m and n, and continue to find the next 1.

    Code:

    class Solution {
    public:
    int largestK(int num ) {
    int k = 0;
    while (num > 1) {
    num = num >>1;
    k++;
    }
    return pow(2,k);
    }

    int rangeBitwiseAnd(int m, int n) {
        if ( m == 0 ) return 0;
        
        int k1 = largestK(m); int k2 = largestK(n);
        
        if (k1 != k2 ) return 0;
        
        int result = k1 + rangeBitwiseAnd(m-k1,n-k1);
        return result;
        
    }
    

    };


Log in to reply
 

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