We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Prime Number of Set Bits in Binary Representation

Difficulty: Easy

Problem Description

Given two integers left and right, return the count of numbers in the inclusive range [left, right] having a prime number of set bits in their binary representation.

Key Insights

  • The number of set bits in an integer can be found using bit manipulation.
  • A prime number is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers.
  • Precompute prime numbers up to a certain limit using the Sieve of Eratosthenes to efficiently check if the count of set bits is prime.
  • The maximum possible set bits for numbers up to 10^6 is limited since 10^6 in binary has at most 20 bits.

Space and Time Complexity

Time Complexity: O(n log log n) for prime computation and O(m) for checking each number in the range, where n is the upper limit for the sieve and m is the count of numbers in the range. Space Complexity: O(n) for storing prime numbers.

Solution

To solve the problem, we will:

  1. Use a Sieve of Eratosthenes to precompute prime numbers up to 20, since the maximum number of set bits for numbers up to 10^6 is 20.
  2. Iterate through each number in the range [left, right], count the number of set bits, and check if that count is prime.
  3. Maintain a count of numbers whose set bits are prime and return this count.

Code Solutions

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

def count_prime_set_bits(left, right):
    # Precompute prime numbers up to 20
    prime_set = {i for i in range(2, 21) if is_prime(i)}
    count = 0
    
    for num in range(left, right + 1):
        set_bits = bin(num).count('1')  # Count the number of set bits
        if set_bits in prime_set:  # Check if set bits count is prime
            count += 1
            
    return count
← Back to All Questions