Prime Number of Set Bits in Binary Representation: Counting Bits with a Twist
LeetCode Prime Number of Set Bits in Binary Representation (Problem 762) gives you two integers left and right. For every number in the inclusive range [left, right], count how many have a prime number of set bits (1-bits) in their binary representation. Return that count.
For example, with left = 6 and right = 10, the numbers are 6, 7, 8, 9, and 10. Their set bit counts are 2, 3, 1, 2, and 2. Since 2 and 3 are prime but 1 is not, the answer is 4 (all except 8).
Why this problem matters
This problem combines two fundamental skills: counting set bits and checking for primality. Neither is hard on its own, but recognizing that you can precompute the set of small primes and use a fast popcount turns a potentially messy problem into a clean loop. It is a good exercise in composing simple building blocks into a solution.
In interviews, problems like this test whether you can decompose a question into independent subproblems. Once you see that the bit counting and the prime checking are separate concerns, the code writes itself.
The approach
The constraint 1 <= left <= right <= 10^6 tells you that numbers are at most 20 bits long. That means the maximum number of set bits is 20. So you only need to know which numbers from 0 to 20 are prime: 2, 3, 5, 7, 11, 13, 17, and 19.
You can hardcode this set, then iterate through the range and check each number's popcount against it.
For counting set bits, Python's bin(n).count('1') works perfectly. You could also use the n & (n - 1) trick or bit_count() in Python 3.10+. All produce the same result.
def countPrimeSetBits(left, right):
primes = {2, 3, 5, 7, 11, 13, 17, 19}
count = 0
for n in range(left, right + 1):
if bin(n).count('1') in primes:
count += 1
return count
Walking through the algorithm
Let's trace through the range [6, 10]. For each number, we convert to binary, count the set bits, and check if that count is prime.
Step 1: Check number 6
6 = 0110. Two set bits. 2 is prime, so count this number. Running total: 1.
Step 2: Check number 7
7 = 0111. Three set bits. 3 is prime, so count this number. Running total: 2.
Step 3: Check number 8
8 = 1000. One set bit. 1 is not prime, so skip. Running total: 2.
Step 4: Check number 9
9 = 1001. Two set bits. 2 is prime, so count this number. Running total: 3.
Step 5: Check number 10
10 = 1010. Two set bits. 2 is prime, so count this number. Running total: 4.
After processing all five numbers, four of them (6, 7, 9, 10) had a prime set bit count. Only 8 had a non-prime count of 1. So the answer is 4.
The key observation is that the prime check is trivial because the set bit count is always small (at most 20). You do not need a general-purpose primality test. A simple set lookup handles it.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Iterate and count bits | O(n * log(max_val)) where n = right - left + 1 | O(1) |
| With built-in popcount | O(n) assuming O(1) popcount | O(1) |
The loop runs once per number in the range. For each number, counting set bits takes O(log(max_val)) in the worst case (one pass through the bits). Since numbers are bounded at 10^6, that is at most 20 bits, making each iteration effectively constant time. The prime set is fixed at 8 elements, so the lookup is O(1).
Edge cases to watch for
- Single-element range (
left = right): The loop runs once. Check whether that single number has a prime set bit count and return 0 or 1. - Powers of two: These always have exactly 1 set bit. Since 1 is not prime, powers of two never contribute to the count.
- All bits set: A number like 7 (111) has 3 set bits, and 3 is prime. Numbers with all bits set in a small range tend to have prime set bit counts because 2, 3, 5, and 7 are all prime.
- Zero set bits: Zero itself has 0 set bits, but the constraint guarantees
left >= 1, so you will not encounter 0 in the range. - Large ranges: With
rightup to 10^6, the loop runs at most one million iterations. Each iteration is constant work, so performance is not a concern.
The building blocks
Popcount (counting set bits). This is the same skill from problems like Number of 1 Bits and Counting Bits. Whether you use bin(n).count('1'), Brian Kernighan's trick, or a built-in, the goal is the same: count how many bits are 1.
Small prime lookup. Since the set bit count is bounded (at most 20 for numbers up to 10^6), you do not need a sieve or trial division. A hardcoded set of primes up to 20 covers every possible case. Recognizing this constraint simplifies the problem significantly.
Range iteration pattern. Many easy LeetCode problems ask you to check a property for every element in a range and count how many satisfy it. The structure is always the same: loop, check, increment. The interesting part is what you check, not the loop itself.
From understanding to recall
This problem is simple once you see the decomposition: count bits, check primality against a small set. But under interview pressure, the trick is remembering to precompute the prime set rather than writing a general primality test for each number.
The recall anchor: "set bit counts are tiny (at most 20), so hardcode the primes." Once that sentence is automatic, you will not waste time on unnecessary complexity.
Practice this a few times over the next week. Each rep should take under two minutes. The goal is not just to solve it, but to solve it instantly, without hesitation, from a blank editor.
Related posts
- Number of 1 Bits - The core popcount technique used to count set bits in each number
- Counting Bits - Building an array of set bit counts using dynamic programming, the batch version of popcount
- Hamming Distance - Combines XOR with popcount to measure how two numbers differ in their binary representations