Skip to main content

762. Prime Number of Set Bits in Binary Representation

easy

Count 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 Alex Chen, 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^6
  • 0 <= right - left <= 10^4

Examples

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). 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). 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.

Output

Press Run or Cmd+Enter to execute

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

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • LinkedIn

Practice these live with InterviewChamp.AI

Drill Prime Number of Set Bits in Binary Representation and Bit Manipulation problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →