Bitwise AND of Numbers Range

📋

Problem

Imagine you want to find the common bits set to 1 in all numbers between two given integers, like finding the shared traits in a family tree of numbers.

Given two integers left and right, return the bitwise AND of all numbers in the inclusive range [left, right]. Input: Two integers left and right. Output: An integer representing the bitwise AND of all numbers from left to right inclusive.

0 <= left <= right <= 2^31 - 1The range size can be large, up to 2^31

Edge cases: left == right → output is left (single number)left = 0, right = 0 → output is 0left = 0, right = large number → output is 0

</>

IDE

def rangeBitwiseAnd(left: int, right: int) -> int:public int rangeBitwiseAnd(int left, int right)int rangeBitwiseAnd(int left, int right)function rangeBitwiseAnd(left, right)

def rangeBitwiseAnd(left: int, right: int) -> int:
    # Write your solution here
    pass

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int rangeBitwiseAnd(int left, int right) {
    // Write your solution here
    return 0;
}

function rangeBitwiseAnd(left, right) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Returning 0 for all inputs without computing common prefix bits.✅ Implement shift-until-equal logic to find common prefix bits before shifting back.

Wrong: leftReturning left without considering the range, ignoring bits that differ.✅ Shift left and right until equal to find common prefix bits, do not return left directly unless left == right.

Wrong: Incorrect non-zero for large rangeUsing brute force that times out or partial loops that do not cover full range.✅ Use O(log n) bit shifting approach instead of brute force iteration.

Wrong: Wrong output for single element rangeNot handling base case when left == right.✅ Add base case: if left == right, return left immediately.

Wrong: Off-by-one error outputLoop or shift logic excludes right boundary.✅ Ensure loops or shifts include right boundary in computation.

✓

Test Cases

Focus on handling boundary cases like single elements and zero ranges.

Watch out for common algorithmic traps like off-by-one and greedy mistakes.

Optimize your solution to run in logarithmic time using bit shifts.

t1_01basic

Input{"left":5,"right":7}

Expected4

⏱ Performance - must finish in 2000ms

5 (0101) & 6 (0110) & 7 (0111) = 4 (0100)

💡 Consider how bits change from left to right in the range.

💡 Look for the common prefix bits of left and right by shifting.

💡 Shift both numbers right until equal, then shift back left.

Why it failed: Incorrect output means failure to find common prefix bits. Fix by shifting left and right rightwards until equal, then shift back.

✓ Correctly found common prefix bits and computed bitwise AND.

t1_02basic

Input{"left":0,"right":1}

Expected0

⏱ Performance - must finish in 2000ms

0 (0000) & 1 (0001) = 0 (0000)

💡 Check how the least significant bits differ in the range.

💡 If any bit flips from 0 to 1 in the range, AND will clear it.

💡 Use shifting to find common prefix bits that remain set.

Why it failed: Wrong output likely from not handling small ranges correctly. Fix by ensuring loop or shift logic covers ranges of size 1.

✓ Correctly handled small range and computed bitwise AND.

t2_01edge

Input{"left":0,"right":0}

Expected0

⏱ Performance - must finish in 2000ms

Single number 0, AND is 0.

💡 Consider the case when left equals right.

💡 The AND of a single number is the number itself.

💡 Return left immediately if left == right.

Why it failed: Fails to handle single element range, returns incorrect value. Fix by adding base case: if left == right, return left.

✓ Correctly returns single number when left == right.

t2_02edge

Input{"left":0,"right":2147483647}

Expected0

⏱ Performance - must finish in 2000ms

Range covers all 31-bit numbers, AND is 0.

💡 Large range likely clears all bits.

💡 Any bit that flips in the range results in 0 in that bit position.

💡 If left is 0 and right is large, result is 0.

Why it failed: Fails to handle large ranges, returns non-zero. Fix by using shift-until-equal approach to detect zero result.

✓ Correctly returns 0 for large range covering all bits.

t2_03edge

Input{"left":7,"right":7}

Expected7

⏱ Performance - must finish in 2000ms

Single number 7, AND is 7.

💡 Single element range returns the element itself.

💡 Check for equality of left and right before processing.

💡 Return left if left == right.

Why it failed: Fails single element case, returns wrong output. Fix by adding base case for left == right.

✓ Correctly returns the single number when left == right.

t3_01corner

Input{"left":6,"right":7}

Expected6

⏱ Performance - must finish in 2000ms

6 (0110) & 7 (0111) = 6 (0110), tests off-by-one range.

💡 Check how your code handles ranges differing by 1.

💡 Ensure you do not skip the last number in the range.

💡 Verify loop or shift logic includes right boundary.

Why it failed: Off-by-one error: last number excluded from AND. Fix by including right in loop or shift logic.

✓ Correctly handles ranges differing by 1.

t3_02corner

Input{"left":4,"right":15}

Expected0

⏱ Performance - must finish in 2000ms

Range 4 to 15 covers bits that flip, result is 0.

💡 Beware of greedy approaches that pick only left or right.

💡 Check all bits that differ in the range.

💡 Use shifting until left == right to find common prefix.

Why it failed: Greedy approach picking left or right directly fails here. Fix by shifting both until equal to find common prefix bits.

✓ Correctly finds common prefix bits for range.

t3_03corner

Input{"left":0,"right":1}

Expected0

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 vs unbounded range logic.

💡 Check if your solution assumes unbounded repetition of bits.

💡 Remember this is a 0/1 range, not unbounded.

💡 Use shift-until-equal approach, not bit clearing loops.

Why it failed: Confuses 0/1 range with unbounded bit clearing, returns wrong output. Fix by using shift-until-equal method.

✓ Correctly handles 0/1 range with shift-until-equal.

t4_01performance

Input{"left":0,"right":2147483647}

Expectednull

⏱ Performance - must finish in 2000ms

Maximum range size (2^31 - 1), O(log(right)) solution must complete within 2s.

💡 Brute force O(right-left) will time out here.

💡 Use bit shifting to find common prefix bits efficiently.

💡 Shift left and right rightwards until equal, then shift back.

Why it failed: Brute force approach causes TLE on large input. Fix by implementing O(log n) shift-until-equal approach.

✓ Efficient O(log n) approach confirmed by passing performance test.

Practice

1. What is the output of the following code when the input is 11?

def hammingWeight(n: int) -> int:
    return bin(n).count('1')

print(hammingWeight(11))

easy

A. 2

B. 4

C. 3

D. 1

Solution

1. Step 1: Convert 11 to binary

   11 in binary is 1011.

2. Step 2: Count '1's in '1011'

   There are three '1's in the string.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   bin(11) = '0b1011', count('1') = 3 [OK]

Hint: Count '1's in binary string representation [OK]

Common Mistakes:

• Counting bits incorrectly
• Confusing decimal and binary digits

2. The following code attempts to count set bits for all numbers from 0 to n using Brian Kernighan's trick. Identify the line containing the subtle bug that causes incorrect results.

def countBits(n):
    res = []
    for i in range(1, n + 1):
        count = 0
        x = i
        while x:
            x &= x - 1
            count += 1
        res.append(count)
    return res

medium

A. Line 3: for i in range(1, n + 1):

B. Line 2: res = []

C. Line 5: while x:

D. Line 7: res.append(count)

Solution

1. Step 1: Check loop range correctness

   The loop starts from 1, missing 0, so the count for 0 is never computed or appended.

2. Step 2: Consequence of missing 0

   Result array length is n instead of n+1, causing mismatch and incorrect output for input including 0.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Including 0 is required to match problem specification [OK]

Hint: Loop must start at 0 to include zero count [OK]

Common Mistakes:

• Starting loop at 1 instead of 0
• Appending before counting
• Incorrect while condition

3. What is the time complexity of the optimal bitmasking solution that sorts words by length and prunes pairs early when finding the maximum product of word lengths with no common letters?

medium

A. O(n^3) due to triple nested loops over words and characters

B. O(n^2 * k) because each pair requires checking all characters

C. O(n^2 + n*k + n log n) where n is number of words and k is average word length

D. O(n log n) since sorting dominates the runtime

Solution

1. Step 1: Analyze preprocessing steps

   Computing bitmasks takes O(n*k) where k is average word length. Sorting masks by length takes O(n log n).

2. Step 2: Analyze nested loops with pruning

   Nested loops run O(n^2) in worst case, but pruning reduces unnecessary checks. Bitwise AND checks are O(1).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Combining all steps yields O(n^2 + n*k + n log n) [OK]

Hint: Bitmask checks are O(1), pruning reduces pairs [OK]

Common Mistakes:

• Assuming O(n^2*k) due to character checks per pair
• Ignoring sorting cost
• Confusing recursion stack space with iterative solution

4. Suppose the input array can contain duplicate numbers and missing numbers may appear multiple times (i.e., numbers can be reused). Which modification to the XOR partitioning approach correctly finds the two missing numbers?

hard

A. Use frequency counting with a hash map instead of XOR to handle duplicates.

B. Use the same XOR partitioning approach since duplicates cancel out in XOR.

C. Modify XOR approach to XOR each number multiple times equal to its frequency.

D. Sort the array and scan for missing numbers instead of XOR.

Solution

1. Step 1: Understand impact of duplicates

   Duplicates break XOR approach because XOR assumes each number appears exactly once.

2. Step 2: Choose correct approach

   Frequency counting with a hash map correctly tracks counts and identifies missing numbers even with duplicates.

3. Step 3: Why other options fail

   Same XOR approach fails due to duplicates; modifying XOR by frequency is not feasible; sorting is O(n log n) and less efficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Frequency counting handles duplicates correctly [OK]

Hint: XOR fails with duplicates; frequency map handles counts [OK]

Common Mistakes:

• Assuming XOR works with duplicates
• Trying to XOR multiple times per frequency
• Ignoring complexity of sorting

5. Suppose you want to generate a Gray code sequence where each number can be repeated multiple times (i.e., reuse allowed). Which modification to the optimal bitwise formula approach correctly handles this variant?

hard

A. Use brute force backtracking to generate sequences with repeated numbers allowed.

B. Modify the formula to i ^ (i >> 1) but allow duplicates by not enforcing uniqueness in the output list.

C. Use the same XOR formula but generate only n numbers instead of 2^n.

D. No modification needed; the original formula already allows repeated numbers.

Solution

1. Step 1: Understand the reuse constraint

   Allowing repeated numbers breaks the Gray code uniqueness property, so the original formula which generates unique numbers won't work.

2. Step 2: Identify suitable approach

   Brute force backtracking can explore sequences with repeated numbers and enforce the one-bit difference condition without uniqueness constraints.

3. Step 3: Why other options fail

   Original formula always generates unique numbers; simply allowing duplicates in output breaks Gray code definition; generating fewer numbers misses full coverage.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Backtracking is flexible enough to handle reuse constraints [OK]

Hint: Original formula assumes unique numbers; reuse needs backtracking [OK]

Common Mistakes:

• Assuming original formula can be tweaked trivially for reuse
• Thinking fewer numbers still form valid Gray code
• Ignoring uniqueness property of Gray code