Description
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.
- For example,
21written in binary is10101, which has3set bits.
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) 8 -> 1000 (1 set bit, 1 is not 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 set bits, 2 is prime) 11 -> 1011 (3 set bits, 3 is prime) 12 -> 1100 (2 set bits, 2 is prime) 13 -> 1101 (3 set bits, 3 is prime) 14 -> 1110 (3 set bits, 3 is prime) 15 -> 1111 (4 set bits, 4 is not prime) 5 numbers have a prime number of set bits.
Constraints:
1 <= left <= right <= 1060 <= right - left <= 104
Solutions
This solution solves the same problem but is more flexible and robust. Instead of hardcoding the prime numbers (2, 3, 5), it uses an array of all possible primes up to 19 (the maximum bit count for a 32-bit integer). For each number in the range, it converts to binary, counts the ones, and checks if that count exists in the primes array using includes().
Language: javascript(2026-02-21 09:44)DONE
CPU Performance49.06%
Memory Performance33.96%
/**
* @param {number} left
* @param {number} right
* @return {number}
*/
var countPrimeSetBits = function(left, right) {
const primes = [2, 3, 5, 7, 11, 13, 17, 19];
let res = 0;
for (let i = left; i <= right; i++) {
const ones = i.toString(2).split('').filter(x => x === '1').length;
if (primes.includes(ones)) {
res++;
}
}
return res;
};