762. Prime Number of Set Bits in Binary Representation
easyCount how many integers in [left, right] have a prime number of set bits. Constraint observation: right <= 10^6 < 2^20, so prime candidates are a tiny fixed set.
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
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.
Constraints
1 <= left <= right <= 10^60 <= right - left <= 10^4
Examples
Example 1
left = 6, right = 104Explanation: 6 -> 110 (2 set bits, 2 is prime). 7 -> 111 (3 set bits, 3 is 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
left = 10, right = 155Explanation: 10 -> 1010 (2). 11 -> 1011 (3). 12 -> 1100 (2). 13 -> 1101 (3). 14 -> 1110 (3). 15 -> 1111 (4 — not prime). 5 numbers have a prime count.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
right <= 10^6 < 2^20, so popcount is at most 19. Prime values to check: {2, 3, 5, 7, 11, 13, 17, 19} — a tiny constant set.
Hint 2
Don't sieve generally — just hard-code the prime set as a 20-bit lookup mask or a small hash set.
Hint 3
Iterate from left to right, compute popcount, and check membership in the prime set.
Solution approach
Reveal approach
Iterate the range and check popcount membership in a small prime set. Precompute the prime-bit lookup: primes = {2, 3, 5, 7, 11, 13, 17, 19} — exactly the primes <= 19, since right < 2^20. For each x from left to right, compute popcount(x) using any standard routine (Brian Kernighan's loop, the built-in __builtin_popcount, Integer.bitCount, etc.) and increment the answer if the popcount is in primes. O((right - left) * log(max)) — under 10^4 * 20 = 200k operations. O(1) space. Optionally store primes as a bitmask (e.g., (1 << 2) | (1 << 3) | ... ) for a single AND-and-test check.
Complexity
- Time
- O((right - left) log right)
- Space
- O(1)
Related patterns
- bit-manipulation
- math
Related problems
- 191. Number of 1 Bits
- 338. Counting Bits
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
More Bit Manipulation practice problems
- 29. Divide Two Integers
- 78. Subsets
- 89. Gray Code
- 136. Single Number
- 137. Single Number II
- 187. Repeated DNA Sequences
- 190. Reverse Bits
- 191. Number of 1 Bits