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.
Recall that the number of set bits an integer has is the number of 1's present when written in binary.
21 written in binary is 10101, which has 3 set bits.Example 1:
Input: left = 6, right = 10 Output: 4 Explanation: 6 -> 110 (2 set bits, 2 is prime) 7 -> 111 (3 set bits, 3 is prime) 8 -> 1000 (1 set bit, 1 is not prime) 9 -> 1001 (2 set bits, 2 is prime) 10 -> 1010 (2 set bits, 2 is prime) 4 numbers have a prime number of set bits.
Example 2:
Input: left = 10, right = 15 Output: 5 Explanation: 10 -> 1010 (2 set bits, 2 is prime) 11 -> 1011 (3 set bits, 3 is prime) 12 -> 1100 (2 set bits, 2 is prime) 13 -> 1101 (3 set bits, 3 is prime) 14 -> 1110 (3 set bits, 3 is prime) 15 -> 1111 (4 set bits, 4 is not prime) 5 numbers have a prime number of set bits.
Constraints:
1 <= left <= right <= 1060 <= right - left <= 104In #762 Prime Number of Set Bits in Binary Representation, the task is to count numbers in a given range whose binary form contains a prime number of set bits (1s). The key idea is to iterate through every number in the range and compute the number of set bits in its binary representation.
You can count set bits using efficient techniques such as n & (n - 1), which removes the lowest set bit each step, or built-in functions like __builtin_popcount in many languages. After computing the bit count, simply check whether this count is a prime number. Since the maximum number of bits for typical constraints is small (usually ≤ 20), you can predefine a set of prime numbers such as {2,3,5,7,11,13,17,19} for constant-time checks.
This approach keeps the logic simple while leveraging efficient bit manipulation. The overall time complexity depends on the range size and the cost of counting bits, while space usage remains minimal.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterate through range + count set bits + prime check | O(N * log W) | O(1) |
| Using built-in popcount with precomputed primes | O(N) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Write a helper function to count the number of set bits in a number, then check whether the number of set bits is 2, 3, 5, 7, 11, 13, 17 or 19.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Bit manipulation allows you to efficiently count the number of 1s in a binary representation without converting the number to a string. Techniques like n & (n - 1) or built-in popcount operations make the solution faster and cleaner.
Yes, variations of bit manipulation problems like this often appear in technical interviews at companies such as Google, Amazon, and Meta. They test understanding of binary representation, efficient bit counting, and simple mathematical reasoning.
A small hash set or predefined set of prime numbers works well for constant-time prime checks. Since the maximum number of set bits is limited, storing primes like 2, 3, 5, 7, 11, 13, 17, and 19 is sufficient for most constraints.
The optimal approach is to iterate through each number in the given range, count the number of set bits in its binary representation, and check whether that count is a prime number. Using efficient bit counting methods or built-in popcount functions makes this process fast and simple.