Prime Number of Set Bits in Binary Representation — Solution
Prime Number of Set Bits in Binary Representation solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Prime Number of Set Bits in Binary Representation is an easy coding problem on math and bit manipulation, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Math, Bit Manipulation
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given two integers left and right, return the count of numbers in the inclusive range [left, right] whose number of set bits is a prime number.
Example 1
Input: left = 6, right = 10
Output: 4
Explanation: 6, 9 and 10 have two set bits; 7 has three.
Example 2
Input: left = 10, right = 15
Output: 5
Example 3
Input: left = 1, right = 1
Output: 0
Constraints
1 <= left <= right <= 20000right - left <= 200
Hints for Prime Number of Set Bits in Binary Representation
Hint 1
Count the set bits of each number in the range.
Hint 2
That count is small — under 20 — so the primality test is trivial.
Hint 3
You can even hard-code the set of primes below 20 and check membership.
How to solve Prime Number of Set Bits in Binary Representation
Count set bits of each number in the range and test membership in the small set of primes below 20.
Approach
- For each
vin[left, right], compute its popcount. - Count those whose popcount is in
{2, 3, 5, 7, 11, 13, 17, 19}.
Why it works
A 32-bit number has at most 32 set bits and the constraints keep it under 20, so a hard-coded prime set suffices.
Complexity
- Time —
O((right - left) · log right) - Space —
O(1)
Pitfalls
- 1 is not prime — a power of two does not count.
Reference solution
Python
def countPrimeSetBits(left: int, right: int) -> int:
primes = {2, 3, 5, 7, 11, 13, 17, 19}
return sum(1 for v in range(left, right + 1) if bin(v).count("1") in primes)Java
public static int countPrimeSetBits(int left, int right) {
Set<Integer> primes = new HashSet<>(Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19));
int count = 0;
for (int v = left; v <= right; v++) {
if (primes.contains(Integer.bitCount(v))) count++;
}
return count;
}C++
int countPrimeSetBits(int left, int right) {
unordered_set<int> primes = {2, 3, 5, 7, 11, 13, 17, 19};
int count = 0;
for (int v = left; v <= right; v++) {
int bits = 0;
unsigned int x = (unsigned int) v;
while (x) {
bits += (int) (x & 1u);
x >>= 1;
}
if (primes.count(bits) > 0) count++;
}
return count;
}JavaScript
var countPrimeSetBits = function(left, right) {
const primes = new Set([2, 3, 5, 7, 11, 13, 17, 19]);
let count = 0;
for (let v = left; v <= right; v++) {
let bits = 0;
let x = v;
while (x > 0) {
bits += x & 1;
x >>>= 1;
}
if (primes.has(bits)) count++;
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 337 math problems · the whole catalogue
Learn the technique: Bit Manipulation