algoadvance

The problem is stated as follows:

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

Clarifying Questions

  1. Range Constraints: What are the lower and upper bounds of the range [left, right]?
    • Typical constraint ranges are (1 \leq \text{left} \leq \text{right} \leq 10^6).
  2. Number of Set Bits: Is there a specific range for the number of bits counted for the prime determination?
    • Considering a maximum range, it’s up to 20 bits since (2^{19} \approx 10^6).
  3. Prime Number Definition: Only prime numbers greater than 1 should be considered?
    • Yes, standard prime definition applies. Prime numbers include 2, 3, 5, 7, etc.

Strategy

To solve this problem, follow these steps:

  1. Convert Number to Binary: Use Python’s built-in binary conversion to count set bits.
  2. Prime Check: Create a helper function to determine if a number is prime.
  3. Iterate through Range: For each number in the range [left, right], count the set bits and check if that count is prime.
  4. Count Valid Numbers: Maintain a counter for numbers with a prime number of set bits.
  5. Optimization: Use memoization or a precomputed set of known prime numbers up to a reasonable size to optimize the prime check.

Code

def countPrimeSetBits(left: int, right: int) -> int:
    def is_prime(num):
        if num <= 1:
            return False
        if num <= 3:
            return True
        if num % 2 == 0 or num % 3 == 0:
            return False
        i = 5
        while (i * i) <= num:
            if num % i == 0 or num % (i + 2) == 0:
                return False
            i += 6
        return True

    # Precompute the set of all primes up to 19
    prime_set = {i for i in range(2, 20) if is_prime(i)}

    result = 0

    for num in range(left, right + 1):
        set_bits = bin(num).count('1')
        if set_bits in prime_set:
            result += 1

    return result

Time Complexity

  1. Prime Check: The is_prime function runs in (O(\sqrt{p})) time.
  2. Binary Conversion and Count: The bin(num).count('1') runs in (O(\log n)) where (n) is the number being converted.
  3. Iteration Over Range: We iterate through each number in the range [left, right], which runs (O(n)) where (n = \text{right} - \text{left} + 1).

Overall time complexity is approximately (O(n \cdot \log n + \sqrt{p})) where (n) is the range size and (p) the largest number of set bits we need to check for primality.

Example

print(countPrimeSetBits(6, 10))  # Output: 4

This counts numbers 6 to 10 and checks the set bits:

Hence, we get 4 numbers with a prime number of set bits.

Try our interview co-pilot at AlgoAdvance.com