【Leetcode_easy】762. Prime Number of Set Bits in Binary Representation

problem

762. Prime Number of Set Bits in Binary Representation

solution1:

class Solution {
public:
int countPrimeSetBits(int L, int R) {
int res = 0;
int bits = 0;
for(int i=L; i<=R; i++)
{
bits = countBits(i);
if(isPrime(bits) && bits!=1 ) res++;//err...
}
return res;
}
int countBits(int num)
{
int res = 0;
while(num>0)
{
if(num & 1 == 1) res++;
num >>= 1;
}
return res;
}
bool isPrime(int num)
{
for(int i=sqrt(num); i>1; i--)
{
if(num%i==0) return false;
}
return true; }
};

solution2:题目中给了数的大小范围 R <= 106 < 220,那么统计出来的非零位个数cnt只需要检测是否是20以内的质数即可,所以将20以内的质数都放入一个HashSet中,然后统计出来cnt后,直接在HashSet中查找有没有即可。

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 bits = 0;
int tmp = i;
while(tmp){
if(tmp&1 == 1) bits++;
tmp >>= 1;
}
res += primes.count(bits);
}
return res;
}
};

参考

1. Leetcode_easy_762. Prime Number of Set Bits in Binary Representation;

2. Grandyang;

上一篇:Leetcode 762. Prime Number of Set Bits in Binary Representation


下一篇:762. Prime Number of Set Bits in Binary Representation