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 <= 104Problem Overview: Given two integers left and right, count how many numbers in this range have a prime number of set bits (1s) in their binary representation. For each integer, convert it conceptually to binary, count the 1s, and check whether that count is a prime number.
Approach 1: Bit Counting with Set Checking (Time: O(n * log W), Space: O(1))
Iterate through every number from left to right. For each number, count the number of set bits using a popcount operation (such as __builtin_popcount in C++ or bin(x).count('1') in Python). Once you have the count, check whether it belongs to a small predefined set of prime numbers like {2,3,5,7,11,13,17,19}. The key insight is that the maximum number of bits for the constraint range is small, so the possible set-bit counts are limited. This approach is simple, readable, and relies on basic bit manipulation and math concepts.
Approach 2: Optimized Prime Check with Bit Manipulation (Time: O(n), Space: O(1))
This approach removes the explicit prime lookup structure and encodes prime counts inside a bitmask. First compute the number of set bits for each number using a fast popcount operation. Then check primality using a precomputed mask such as 665772, where the binary representation stores which counts are prime. The check becomes (mask >> count) & 1. This turns the prime test into a constant-time bit operation. The idea leverages properties of small primes and keeps the entire solution in pure bitwise arithmetic. It is extremely compact and common in competitive programming solutions involving bit manipulation.
Recommended for interviews: The bit counting with prime set approach is what most interviewers expect first. It clearly shows you understand binary representation, set-bit counting, and basic prime logic. The bitmask optimization is a nice follow-up that demonstrates deeper familiarity with bit tricks and constant-time checks.
This approach involves iterating over each number in the specified range, counting the number of set bits (1s in the binary representation), and checking if the count is a prime number. We use a predefined set of prime numbers up to 19, since the number of set bits can at most be around 20 (using log base 2 of the maximum value 10^6).
In the C implementation, we define helper functions for checking prime status and counting set bits. We iterate from left to right, use the helper function to count the set bits, and check if it is prime.
Time Complexity: O(n * b) where n is the difference between right and left, and b is the number of bits in the binary representation of the number.
Space Complexity: O(1) since we're using a fixed amount of extra space.
This optimized approach employs direct bit manipulation for counting the set bits and uses a bit mask for prime number checking, representing the primality of counts using bits instead of hash sets or arrays.
The C solution uses the GCC-specific built-in function __builtin_popcount for efficient bit counting, combined with bit-masking to check primality. The primes are stored as active bits in an integer representing a mask.
Time Complexity: O(n) with efficient bit manipulations.
Space Complexity: O(1).
In the problem, both left and right are within the range of 10^6, and since 2^{20} = 1048576, the number of 1s in binary representation can be at most 20. The prime numbers within 20 are [2, 3, 5, 7, 11, 13, 17, 19].
We enumerate each number in the range [left,.. right], count the number of 1s in its binary representation, and then check if this count is a prime number. If it is, we increment the answer by one.
The time complexity is O(ntimes log m), where n = right - left + 1 and m is the maximum number in the range [left,.. right].
| Approach | Complexity |
|---|---|
| Bit Counting with Set Checking | Time Complexity: O(n * b) where n is the difference between right and left, and b is the number of bits in the binary representation of the number. |
| Optimized Prime Check with Bit Manipulation | Time Complexity: O(n) with efficient bit manipulations. |
| Math + Bit Manipulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bit Counting with Prime Set Checking | O(n * log W) | O(1) | Best for readability and interviews. Easy to implement with built-in popcount. |
| Optimized Prime Check with Bit Mask | O(n) | O(1) | When you want a compact constant-time prime check using bit manipulation. |
Prime Number of Set Bits in Binary Representation | Simple Approach | Leetcode 762 | MIK • codestorywithMIK • 3,555 views views
Watch 9 more video solutions →Practice Prime Number of Set Bits in Binary Representation with our built-in code editor and test cases.
Practice on FleetCode