Algorithm
Problem Name: 762. Prime Number of Set Bits in Binary Representation
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
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int numOfBits(n) {
int k = 0;
while (n) {
k ++;
n = n & (n - 1);
}
return k;
}
int countPrimeSetBits(int L, int R){
int k = (1 << 2) |
(1 << 3) |
(1 << 5) |
(1 << 7) |
(1 << 11) |
(1 << 13) |
(1 << 17) |
(1 << 19);
int ans = 0;
while (L < = R) {
if ((k >> numOfBits(L)) & 1) ans ++;
/* equals to:
if (numOfBits(L) is 2 or 3 or 5 or 7 ...
*/
}
return ans;
}
Input
left = 6, right = 10
Output
4
#2 Code Example with C++ Programming
Code -
C++ Programming
const countPrimeSetBits = function(L, R) {
let res = 0;
for (let i = L; i < = R; i++) {
if (chkPrime(i)) {
res += 1;
}
}
return res;
};
function chkPrime(num) {
const str = bin(num);
const snum = setNum(str);
return isPrime(snum);
}
function setNum(str) {
let num = 0;
for (let i = 0; i < str.length; i++) {
if (str.charAt(i) === "1") {
num += 1;
}
}
return num;
}
function bin(num) {
return (num >>> 0).toString(2);
}
function isPrime(num) {
for (let i = 2; i < num; i++) {
if (num % i === 0) return false;
}
return num !== 1;
}
Input
left = 6, right = 10
Output
4
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def countPrimeSetBits(self, L, R):
"""
:type L: int
:type R: int
:rtype: int
"""
count=0
while L<=R:
if str(bin(L)[2:]).count("1") in [2,3,5,7,11,13,17,19]: count+=1
if str(bin(R)[2:]).count("1") in [2,3,5,7,11,13,17,19]:
count+=1
if L==R: count-=1
L+=1
R-=1
return count
Input
left = 10, right = 15
Output
5
#4 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0762_PrimeNumberOfSetBitsInBinaryRepresentation
{
public int CountPrimeSetBits(int L, int R)
{
var count = 0;
for (int i = L; i < = R; i++)
{
var bits = CountBits(i);
if (bits == 2 || bits == 3 || bits == 5 || bits == 7 ||
bits == 11 || bits == 13 || bits == 17 || bits == 19)
count++;
}
return count;
}
private int CountBits(int num)
{
var count = 0;
while (num > 0)
{
num &= num - 1;
count++;
}
return count;
}
}
}
Input
left = 10, right = 15
Output
5