Prime Number of Set Bits in Binary Representation

Prime Number of Set Bits in Binary Representation

What is this problem about?

The Prime Number of Set Bits in Binary Representation problem asks you to count integers in [l, r] whose binary representation has a prime number of set bits. This easy coding problem combines bit counting (popcount) with primality checking. The math and bit manipulation interview pattern is demonstrated.

Why is this asked in interviews?

Amazon asks this to test combining two fundamental operations: counting set bits (Brian Kernighan's trick or bin().count('1')) and checking if a small count is prime. Since numbers in [1, 10^6] have at most 20 bits, the prime set count can only be {2,3,5,7,11,13,17,19} — a small fixed set.

Algorithmic pattern used

Popcount + prime set membership. Precompute: prime_set = {2,3,5,7,11,13,17,19} (all primes ≤ 20 = max bit length of 10^6). For each n in [l, r]: count = bin(n).count('1'). If count in prime_set, increment result.

Example explanation

l=6, r=10.

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

Common mistakes candidates make

• Checking primality for every count (unnecessary — precompute the small fixed set).
• Using slow primality test for small counts (trial division is fine but a set is O(1)).
• Forgetting that 1 bit is not prime.
• Off-by-one in range: [l, r] is inclusive on both ends.

Interview preparation tip

Prime Number of Set Bits rewards precomputing: since the maximum number of bits is bounded (≤20), precompute all primes ≤20 into a set. Then the entire problem reduces to two O(1) operations per number. Practice similar "property of binary representation" problems: "count numbers with k set bits in range," "sum of set bits in range." These build fluency with bit counting.