LeetCode 201 Solutions

Problem

Bitwise AND of Numbers Range (LeetCode daily streak)

Description

Given two numbers left and right, we need to compute the bitwise & of every integer in the range [left, right].

Input: left = 5, right = 7
Output: 4

Let's verify by writing out all the numbers in binary:

5 : 101
6 : 110
7 : 111

The only bit that remains 1 across all three values is 100, which equals 4. So the result is 4.

Approach

First Attempt

I wrote out the numbers 1 through 15 in binary and looked for a pattern.

For example:

3 is 011
7 is 111

As we AND all integers from 3 to 7, the range passes through 4 (100), which causes every bit to become 0.

From this, I observed that if two numbers share the same leading bit (i.e., they fall within the same power-of-2 range), that leading bit survives. But if they have different binary lengths — like 3 and 7 — the result is 0.

My first approach was to use the difference between left and right to determine how many trailing bits to zero out:

const diff = right - left
let binary = left.toString(2).split('')
let pow = 1,
  count = 0
while (diff >= pow) {
  pow *= 2
  count++
}
binary = binary.slice(0, binary.length - count)
binary = binary.concat(new Array(count).fill('0'))
const result = parseInt(binary.join(''), 2)

However, I quickly discovered that the difference alone is not sufficient to determine the result.

For example, 11 to 12 and 13 to 14 have the same difference, but produce different results:

1011
1100
// result: 1000(2) = 8

1101
1110
// result: 1100(2) = 12

Second Attempt

I realized the key insight is not the raw difference, but how the numbers relate to the nearest power of 2. I also noticed that the bit-checking process is recursive.

Take the case of 13 and 14:

1101
1110
// Do they share the same leading bit? 1000 ✅
 101
 110
// Do they share the same leading bit? 100 ✅
  01
  10
// No shared leading bit — stop here

The result is the sum of 1000(2) and 100(2), giving 1100(2) = 12.

Solution

/**
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
var rangeBitwiseAnd = function (left, right) {
  if (left == right) {
    return left
  }
  const closeLeft = 1 << (32 - Math.clz32(left))
  const closeRight = 1 << (32 - Math.clz32(right))
  const lowLeft = 1 << (31 - Math.clz32(left))
  if (closeLeft != closeRight) {
    return 0
  }
  return lowLeft + rangeBitwiseAnd(left - lowLeft, right - lowLeft)
}

Retrospect

I still find bit-manipulation problems uncomfortable — it took me over 20 minutes just to recognize the underlying pattern. On top of that, I had to look up bitwise utilities like Math.clz32(), which added to the time. More practice with bit problems is clearly needed.