Bitwise AND of Numbers Range LeetCode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon Facebook NvidiaViews 3794

Problem Statement

Bitwise AND of Numbers Range LeetCode Solution – Given 2 numbers left and right that represent the range [left, right], we have to find bitwise AND of all the numbers from left to right (both inclusive)

Examples & Explanation

Example 1:

Input: left = 5, right = 7
Output: 4
Explanation: 
5 & 6 = 4
4 & 7 = 4
Hence answer is 4

Example 2:

Input: left = 0, right = 0
Output: 0
Explanation:
0 & 0 = 0

Example 3:

Input: left = 1, right = 2147483647
Output: 0
Explanation:
0 & 1 & 2 & ...... & 2147483647 = 0
</code><code class="language-cpp">

Approach

In order to fully understand the problem statement, let’s revisit the concept of bitwise AND. Recall, the bitwise AND takes two operands and does AND on every bit of the two operands. Bitwise AND results in 1 iff both bits are 1 and 0 otherwise.

Brute force idea: iterate from left to right and do the bit AND operation to obtain the final result. However, this will cause TLE for large ranges like in eg. 3.

To come up with a solution with better time complexity, let us take eg. where left = 16 and right = 19. In this example, we can observe that after the AND operation on all the numbers, the remaining part of bit strings is the common prefix of all these bit strings. Therefore, this question asks us to find the common prefix of their binary strings of the given range.

Idea

In order to find the common prefix, perform right shift on left and right and update left as left = left >> 1 and right = right >> 1. Keep a counter “shifts” to count the number of times the right shift operation is performed. Below is the implementation of this idea using the range [16,19]

Bitwise AND of Numbers Range LeetCode Solution

Code

C++ Code for Bitwise AND of Numbers Range LeetCode

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        int shifts=0;
        while(left!=right) {
            left>>=1;
            right>>=1;
            shifts++;
        }
        return left << shifts;
    }
};

Java Code for Bitwise AND of Numbers Range LeetCode

class Solution {
  public int rangeBitwiseAnd(int left, int right) {
    int shifts = 0;
    while (left != right) {
      left >>= 1;
      right >>= 1;
      shifts++;
    }
    return left << shifts;
  }
}

Python Code for Bitwise AND of Numbers Range LeetCode

class Solution(object):
    def rangeBitwiseAnd(self, left, right):
        """
        :type left: int
        :type right: int
        :rtype: int
        """
        shift = 0   
        while left != right:
            left = left >> 1
            right = right >> 1
            shift += 1
        return left << shift

Complexity Analysis for Bitwise AND of Numbers Range LeetCode Solution

  • Time Complexity: O(1)
    • The loop used in the algorithm is bounded by the number of bits that the integer has, since the number of bits is fixed, the time complexity becomes constant in time
  • Space Complexity: 
    • The only variable used in this algorithm is “shifts” and hence space complexity is also constant regardless of input size
Translate »