Domain 1EasyCORE

Prime Number of Set Bits in Binary Representation

The problem requires counting numbers within a given range `[L, R]` that have a prime number of set bits in their binary representation. The inputs are two integers `L` and `R`, where `1 <= L <= R <= 10^6`. The output is an integer representing the count of such numbers.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Bit Manipulation

762. Prime Number of Set Bits in Binary Representation

Model: qwen2.5-coder:14b
Topics: Bit Manipulation
FAANG asked: 1
Acceptance rate: 64.6%


Problem Breakdown

The problem requires counting numbers within a given range [L, R] that have a prime number of set bits in their binary representation. The inputs are two integers L and R, where 1 <= L <= R <= 10^6. The output is an integer representing the count of such numbers.

Inputs:

  • Two integers L and R.

Outputs:

  • An integer representing the count of numbers with a prime number of set bits in their binary representation within the range [L, R].

Implicit Constraints/Edge Cases:

  • The range [L, R] can be large, up to 10^6.
  • The difference R - L is at most 10000.
  • Edge cases include when L and R are close together or when the range includes numbers with very few set bits.

Intuition

A brute-force approach would involve iterating through each number in the range [L, R], converting it to binary, counting the set bits, checking if this count is a prime number, and then summing up all such occurrences. This approach is inefficient due to its high time complexity, especially given the constraints.

The key insight is to optimize the process of checking for prime numbers by precomputing a list of prime numbers up to a reasonable limit (since the maximum number of set bits in any number within the range [1, 10^6] is 20). This allows us to quickly check if the count of set bits is prime.

Approach

  1. Precompute Prime Numbers: Create a list of prime numbers up to 20 since the maximum number of set bits in any number within the range [1, 10^6] is 20.
  2. Iterate Through Range: For each number n in the range [L, R], count the number of set bits using bit manipulation.
  3. Check for Prime Count: Use the precomputed list to check if the count of set bits is a prime number.
  4. Count Valid Numbers: Maintain a counter to keep track of numbers that have a prime number of set bits.

Complexity Analysis

  • Time Complexity: O(N * k), where N is the length of the range [L, R] and k is the maximum number of bits in any number within this range (which is 20). The precomputation step for primes is O(1) since it’s a fixed operation.
  • Space Complexity: O(1) for the prime list and other variables used.

Solution

def countPrimeSetBits(L, R):
    # Precompute prime numbers up to 20
    primes = [False] * 21
    for num in range(2, 21):
        is_prime = True
        for i in range(2, int(num ** 0.5) + 1):
            if num % i == 0:
                is_prime = False
                break
        primes[num] = is_prime
    
    count = 0
    for n in range(L, R + 1):
        # Count the number of set bits in the binary representation of n
        set_bits_count = bin(n).count('1')
        # Check if the count of set bits is a prime number
        if primes[set_bits_count]:
            count += 1
    
    return count

# Example usage:
print(countPrimeSetBits(6, 10))  # Output: 4
print(countPrimeSetBits(10, 15)) # Output: 5

Edge Cases Handled

  • Small Range: The code efficiently handles ranges with a small number of elements.
  • Large Range: Given the constraints, the code is optimized to handle large ranges up to [1, 10^6].
  • Prime Check Optimization: Precomputing prime numbers ensures that checking for primality is done in constant time.