Problem Description

You need to find how many numbers in a given range have a special property: the count of 1s in their binary representation must be a prime number.

Given two integers left and right, count all numbers from left to right (inclusive) where the number of 1 bits in the binary form is prime.

For example:

• The number 21 in binary is 10101
• It has three 1 bits (at positions 1, 3, and 5)
• Since 3 is a prime number, 21 would be counted

The solution works by:

1. Creating a set of prime numbers up to 19 (since the maximum possible bit count for 32-bit integers is around 20)
2. For each number in the range [left, right], using bit_count() to count the 1 bits
3. Checking if this count exists in the prime set
4. Summing up all numbers that satisfy the condition

The key insight is that we only need to check primality for small numbers (up to about 20) since that's the maximum number of set bits possible in the given constraints.

Intuition

The first observation is that we need to count set bits (1s) in binary representation for each number in our range. Since we're dealing with 32-bit integers, the maximum number of set bits any number can have is 32.

This leads to a crucial insight: we only need to determine which numbers from 0 to 32 are prime. This is a small, fixed set that we can precompute. The prime numbers up to 32 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31.

In practice, for the typical constraints of this problem (numbers up to around 10^6), we'll never see numbers with more than 20 set bits. For example, 2^20 - 1 = 1,048,575 has 20 set bits and is already over a million. This means we can optimize our prime set to only include primes up to 19 or 20.

The straightforward approach becomes:

1. For each number in the range, count its set bits
2. Check if that count is prime
3. Keep a running total

Since checking if a small number (≤32) is prime is O(1) using a precomputed set, and counting bits is also O(1) with built-in functions like bit_count(), the entire solution is linear in the size of the range.

The elegance of this solution comes from recognizing that we're not checking if the numbers themselves are prime (which would be expensive), but rather checking if the bit count is prime - and bit counts are always small numbers that we can handle efficiently with precomputation.

Learn more about Math patterns.

Solution Approach

The implementation uses a direct counting approach with precomputed primes:

Step 1: Precompute Prime Numbers

primes = {2, 3, 5, 7, 11, 13, 17, 19}

We create a set containing all prime numbers up to 19. Using a set gives us O(1) lookup time when checking if a bit count is prime. The number 19 is sufficient because numbers in the typical constraint range won't have more than 19-20 set bits.

Step 2: Iterate Through the Range

for i in range(left, right + 1)

We examine each number from left to right inclusive. The + 1 ensures we include the right boundary.

Step 3: Count Set Bits and Check Primality

i.bit_count() in primes

For each number i:

• i.bit_count() returns the number of 1s in the binary representation
• We check if this count exists in our prime set
• This expression evaluates to True (counted as 1) or False (counted as 0)

Step 4: Sum the Results

sum(i.bit_count() in primes for i in range(left, right + 1))

The generator expression produces a sequence of boolean values (True/False). Python's sum() function treats True as 1 and False as 0, giving us the total count of numbers with a prime number of set bits.

Time Complexity: O(n) where n = right - left + 1, since we check each number once and both bit_count() and set lookup are O(1) operations.

Space Complexity: O(1) as we only store a fixed-size set of primes regardless of input size.

Example Walkthrough

Let's walk through the solution with left = 6 and right = 10.

Step 1: Set up our prime numbers

primes = {2, 3, 5, 7, 11, 13, 17, 19}

Step 2: Check each number in the range [6, 10]

For i = 6:

• Binary representation: 110
• Count of 1s: 2
• Is 2 prime? Yes (2 is in our prime set)
• Count this number ✓

For i = 7:

• Binary representation: 111
• Count of 1s: 3
• Is 3 prime? Yes (3 is in our prime set)
• Count this number ✓

For i = 8:

• Binary representation: 1000
• Count of 1s: 1
• Is 1 prime? No (1 is not in our prime set)
• Don't count this number ✗

For i = 9:

• Binary representation: 1001
• Count of 1s: 2
• Is 2 prime? Yes (2 is in our prime set)
• Count this number ✓

For i = 10:

• Binary representation: 1010
• Count of 1s: 2
• Is 2 prime? Yes (2 is in our prime set)
• Count this number ✓

Step 3: Sum up the results

• Numbers with prime bit counts: 6, 7, 9, 10
• Total count: 4

The solution code would execute this as:

primes = {2, 3, 5, 7, 11, 13, 17, 19}
result = sum(i.bit_count() in primes for i in range(6, 11))
# Generates: True, True, False, True, True
# Sum: 1 + 1 + 0 + 1 + 1 = 4

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n = right - left + 1

The algorithm iterates through each number from left to right inclusive, which gives us n iterations. For each number i in this range:

• i.bit_count() operation takes O(1) time in Python (implemented as a built-in method that counts set bits efficiently)
• Checking membership in the primes set takes O(1) average time
• The sum operation accumulates these results

Therefore, the overall time complexity is O(n) * O(1) = O(n).

Space Complexity: O(1)

The space usage consists of:

• The primes set containing exactly 8 elements (all prime numbers less than 20, since the maximum number of bits in a 32-bit integer is 32, and we only need primes up to 19), which takes O(1) space
• The generator expression in the sum function doesn't create an intermediate list, it processes elements one at a time, using O(1) additional space
• Variables for iteration and counting use O(1) space

The space complexity remains constant regardless of the input range size, making it O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Determining the Range of Prime Numbers Needed

A common mistake is either using too few primes (missing valid cases) or calculating primes dynamically (inefficient). Developers might assume they need primes up to 32 (thinking of 32-bit integers) or might not realize the actual maximum bit count for their input constraints.

Pitfall Example:

# Wrong: Missing necessary primes
primes = {2, 3, 5, 7}  # Too few primes

# Wrong: Overcomplicated prime generation
def is_prime(n):
    if n < 2: return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0: return False
    return True

# Checking primality for each bit count repeatedly
for num in range(left, right + 1):
    if is_prime(num.bit_count()):
        count += 1

Solution: Precompute the exact set of primes needed based on constraints. For numbers up to 10^6 (approximately 2^20), the maximum bit count is 20, so primes up to 19 are sufficient:

primes = {2, 3, 5, 7, 11, 13, 17, 19}

2. Using Manual Bit Counting Instead of Built-in Methods

Developers might implement their own bit counting logic, which is error-prone and less efficient than built-in methods.

Pitfall Example:

# Wrong: Manual bit counting with potential errors
def count_bits(n):
    count = 0
    while n > 0:
        count += n & 1
        n = n >> 1  # Could forget this shift
    return count

# Or using string conversion (less efficient)
bin_str = bin(num)[2:]  # Remove '0b' prefix
bit_count = bin_str.count('1')

Solution: Use Python's built-in bit_count() method (Python 3.10+) or bin(num).count('1') for older versions:

# Python 3.10+
set_bits = num.bit_count()

# Python < 3.10
set_bits = bin(num).count('1')

3. Off-by-One Errors with Range Boundaries

Forgetting that the range should be inclusive of both boundaries is a frequent mistake.

Pitfall Example:

# Wrong: Excludes the right boundary
for num in range(left, right):  # Missing right + 1
    # ... processing

# Wrong: Including unnecessary numbers
for num in range(left - 1, right + 2):  # Too broad
    # ... processing

Solution: Always use range(left, right + 1) to include both boundaries:

for num in range(left, right + 1):
    # Process each number in [left, right] inclusive

4. Inefficient Prime Checking with Lists Instead of Sets

Using a list for prime storage leads to O(n) lookup time instead of O(1).

Pitfall Example:

# Wrong: Using list leads to slower lookups
primes = [2, 3, 5, 7, 11, 13, 17, 19]
if set_bits_count in primes:  # O(n) lookup
    count += 1

Solution: Use a set for constant-time lookups:

primes = {2, 3, 5, 7, 11, 13, 17, 19}  # Set for O(1) lookup
if set_bits_count in primes:
    count += 1