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.