762. Prime Number of Set Bits in Binary Representation

Given two integers `L` and `R`, find the count of numbers in the range `[L, R]` (inclusive) 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, `21` written in binary is `10101` which has 3 set bits. Also, 1 is not a prime.)

Example 1:

``````Input: L = 6, R = 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)
``````

Example 2:

``````Input: L = 10, R = 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)
``````

Note:

1. `L, R` will be integers `L <= R` in the range `[1, 10^6]`.
2. `R - L` will be at most 10000.

``````class Solution {
public:
int countPrimeSetBits(int L, int R) {
int res = 0;
for (int i = L; i <= R; ++i) {
int t = i, cnt = 0;
while (t > 0) {
if (t & 1 == 1) ++cnt;
t >>= 1;
}
bool succ = true;
for (int j = sqrt(cnt); j > 1; --j) {
if (cnt % j == 0) {
succ = false; break;
}
}
if (succ && cnt != 1) ++res;
}
return res;
}
};
``````

``````class Solution {
public:
int countPrimeSetBits(int L, int R) {
int res = 0;
unordered_set<int> primes{2, 3, 5, 7, 11, 13, 17, 19};
for (int i = L; i <= R; ++i) {
int cnt = 0;
for (int j = i; j > 0; j >>= 1) {
cnt += j & 1;
}
res += primes.count(cnt);
}
return res;
}
};
``````

``````class Solution {
public:
int countPrimeSetBits(int L, int R) {
int res = 0;
for (int i = L; i <= R; ++i) {
int cnt = __builtin_popcount(i);
res += cnt < 4 ? cnt > 1 : (cnt % 2 && cnt % 3);
}
return res;
}
};
``````

Number of 1 Bits

https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/discuss/113225/Short-C++-12-ms

https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/discuss/113227/JavaC++-Clean-Code

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation