Problem Description
Given two integers left and right, count the numbers in the inclusive range [left, right] that have a prime number of set bits (1's) in their binary representation.
Key Insights
- Convert each number to its binary representation.
- Count the number of set bits (1's) in the binary form.
- Use a precomputed set of prime numbers (only small primes are needed since numbers are at most 20 bits long).
- Check for each number if its set bit count is in the prime set.
- Increment the counter for every number meeting the condition.
Space and Time Complexity
Time Complexity: O(n * log(right)), where n is the number of integers in the range and log(right) accounts for counting the bits. Space Complexity: O(1), as only a fixed-size set of primes and a few variables are used.
Solution
We iterate over every number in the range [left, right]. For each number, we compute the number of 1's in its binary representation—this can be done using built-in functions or bit manipulation. Since the maximum bits required for representing numbers up to 10^6 is around 20, the maximum possible count is small. We then check if this count is among the precomputed prime numbers (2, 3, 5, 7, 11, 13, 17, and 19). If it is, we increment our answer counter. Finally, we return the counter.