Prime Number of Set Bits in Binary Representation
Easy · Bit Manipulation · Math · Bit Manipulation
Problem
You are given two integers left and right. For each integer in the inclusive range [left, right], count the 1 bits in its binary form (its set bits).
Return how many numbers in the range have a prime number of set bits. Remember that 1 is not prime.
Examples
Input: left = 10, right = 15 Output: 5
10, 11, 12, 13 and 14 have 2, 3, 2, 3 and 3 set bits, all prime; 15 (1111) has 4.
Input: left = 1, right = 4 Output: 1
Only 3 (11) has a prime count; 1, 2 and 4 each have a single set bit.
Input: left = 6, right = 10 Output: 4
6 (110), 7 (111), 9 (1001) and 10 (1010) have 2, 3, 2 and 2 set bits; 8 (1000) has 1.
Constraints
- 1 <= left <= right <= 10^6
- 0 <= right - left <= 10^4
Approaches
- Baseline: shift out the bits, test primality by division — time O(r · log right), space O(1)
Follow-up
The range here is at most 10^4 + 1 numbers, so checking each one is fine. If the range could hold 10^15 numbers, count by bit positions instead: the numbers up to n with exactly c set bits come from choosing where the ones go below each set bit of n. The first use case asks exactly that.
Related problems
Start free on Cariara · Coding problems · System design studio
