A Unique O(1) Solution in C# With Detailed Explanation


  • 0
    R

    We can see after some careful observation that:

    1. If the number of bits of binary representation of these numbers is different, the result is automatically 0. Because, let's say if the number of bits is different, as we're going up, we'll get to the number that has 1 more bit than the previous one, that number will be a power of 2 and will have the form 1000... cancelling out all other bits in the result.

    2. Now that we know we're dealing with numbers of same bit length, we can do a little further observation and see the below pattern:

      • If the difference between these two nums is 1, the last bit of the AND of all numbers will definitely be 0.
      • If the difference between these two nums is 2, the last 2 bits of the AND of all numbers will definitely be 0.
      • If the difference between these two nums is 3, the last 2 bits of the AND of all numbers will definitely be 0.
      • If the difference between these two nums is 4, the last 3 bits of the AND of all numbers will definitely be 0.

    This pattern shows us that the last N bits of the result will definitely be 0, where N is the number of bits of the difference between two numbers.
    So we construct a mask to satisfy this and get the result by AND'ing num1, num2 and the mask.
    (Actually the complexity will be dependent on the number of bits in the numbers, since we're counting the bits, but it's usually OK to assume that the number of bits is a constant number since it's max 32)
    Here's my code:

    public class Solution {
        public int RangeBitwiseAnd(int m, int n) 
        {
            int numBits1 = GetNumBits(m);
            int numBits2 = GetNumBits(n);
            
            if(numBits1 != numBits2)
                return 0;
                
            int diffNumBits = GetNumBits(Math.Abs(m-n));
            int mask = (int)(Math.Pow(2, numBits1) - 1);
            mask -= (int)(Math.Pow(2, diffNumBits) - 1);
            
            return m & n & mask;
        }
        
        public int GetNumBits(int n)
        {
            int bits = 0;
            while(n > 0)
            {
                n = n >> 1;
                ++bits;
            }
            
            return bits;
        }
    }
    

Log in to reply
 

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