Code Implementation

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        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

        primes = {2, 3, 5, 7, 11, 13, 17, 19}
        count = 0
        for num in range(left, right + 1):
            set_bits = bin(num).count('1')
            if set_bits in primes:
                count += 1
        return count
      

class Solution {
public:
    bool isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; i * i <= n; ++i) {
            if (n % i == 0) return false;
        }
        return true;
    }
    int countPrimeSetBits(int left, int right) {
        int primes[] = {2, 3, 5, 7, 11, 13, 17, 19};
        std::unordered_set<int> primeSet(primes, primes + 8);
        int count = 0;
        for (int num = left; num <= right; ++num) {
            int setBits = __builtin_popcount(num);
            if (primeSet.count(setBits)) {
                ++count;
            }
        }
        return count;
    }
};
      

class Solution {
    public int countPrimeSetBits(int left, int right) {
        int[] primes = {2, 3, 5, 7, 11, 13, 17, 19};
        Set<Integer> primeSet = new HashSet<>();
        for (int p : primes) primeSet.add(p);
        int count = 0;
        for (int num = left; num <= right; num++) {
            int setBits = Integer.bitCount(num);
            if (primeSet.contains(setBits)) {
                count++;
            }
        }
        return count;
    }
}
      

var countPrimeSetBits = function(left, right) {
    const primes = new Set([2, 3, 5, 7, 11, 13, 17, 19]);
    let count = 0;
    for (let num = left; num <= right; num++) {
        let setBits = num.toString(2).split('1').length - 1;
        if (primes.has(setBits)) {
            count++;
        }
    }
    return count;
};
      

Problem Description

The problem asks you to count how many numbers in a given range, from left to right (inclusive), have a prime number of set bits in their binary representation.

A set bit is a bit with value 1. For each integer in the range, you convert it to binary, count the number of 1's (set bits), and check if that count is a prime number. If it is, you increment your answer.

Constraints:

• Each number in the range is considered exactly once.
• The range is inclusive of both left and right.
• There is only one way to count the set bits for a number.
• No elements are reused; each number is checked independently.

Thought Process

At first glance, the problem seems to require checking each number in the range, converting it to binary, counting the set bits, and then checking if that count is a prime number. This approach is straightforward but could be slow if the range is large.

To optimize, we can make two observations:

• The number of set bits in a number is always between 0 and the number of bits required to represent right (which is at most 20 for the problem's constraints).
• We can precompute which numbers between 0 and 20 are prime and use a set or array for constant-time lookup.

Solution Approach

Let's break down the optimized solution step by step:

1. Precompute Prime Numbers:
   • The possible number of set bits for any number in the range is small (at most 20).
   • We can create a set of prime numbers up to 20: {2, 3, 5, 7, 11, 13, 17, 19}.
2. Iterate Through the Range:
   • Loop from left to right (inclusive).
3. Count Set Bits:
   • For each number, count the number of 1's in its binary representation.
   • Most languages have a built-in or easy way to do this (e.g., bin(num).count('1') in Python).
4. Check for Primality:
   • Check if the set bit count is in our precomputed set of primes.
5. Accumulate the Result:
   • If the set bit count is prime, increment a counter.

Example Walkthrough

Let's walk through an example with left = 6 and right = 10:

• 6: Binary is 110 (2 set bits). 2 is prime. Count = 1
• 7: Binary is 111 (3 set bits). 3 is prime. Count = 2
• 8: Binary is 1000 (1 set bit). 1 is not prime. Count = 2
• 9: Binary is 1001 (2 set bits). 2 is prime. Count = 3
• 10: Binary is 1010 (2 set bits). 2 is prime. Count = 4

Time and Space Complexity

Brute-force Approach:

• For each number in the range, count set bits (up to O(logN)) and check primality (up to O(sqrt(logN))).
• Time: O((right - left + 1) * logN)
• Space: O(1) (no extra data structures needed)

• Precompute primes up to 20 (constant time and space).
• For each number, counting set bits and checking primality are both O(1) due to small bit size and set lookup.
• Time: O(right - left + 1)
• Space: O(1) (since the set of primes is small and fixed)

Summary

The key insight in this problem is recognizing that the number of set bits is always small, so we can precompute which counts are prime and check them quickly. By iterating through the range, counting set bits efficiently, and using a set for primality lookup, we achieve an elegant and highly efficient solution. This approach avoids unnecessary computation and leverages language features for clean, readable code.