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 1s 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:

L, R will be integers L >= R in the range [1, 10^6].
R – L will be at most 10000.

Hints:
Write a helper function to count the number of set bits in a number, then check whether the number of set bits is 2, 3, 5, 7, 11, 13, 17 or 19.

As the input integers are quite small (L,R smaller than 10^6 which is smaller than 2^20). We know the prime numbers up to 20. Thus, checking each numbers in the range and check the set bit count is prime should be trivial to do so.

C++ BitSet count Prime Algorithm

In C++, we can use the bitset class to count() the number of bits that are 1’s. For example:

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int countPrimeSetBits(int L, int R) {
        int ans = 0;
        for (int x = L; x <= R; ++ x) {
            int bc = bitset<32>(x).count();
            if (bc == 2 || bc == 3 || bc == 5 || bc == 7 ||
                bc == 11 || bc == 13 || bc == 17 || bc == 19) ans ++;
        }
        return ans;        
    }
};

class Solution {
public:
    int countPrimeSetBits(int L, int R) {
        int ans = 0;
        for (int x = L; x <= R; ++ x) {
            int bc = bitset<32>(x).count();
            if (bc == 2 || bc == 3 || bc == 5 || bc == 7 ||
                bc == 11 || bc == 13 || bc == 17 || bc == 19) ans ++;
        }
        return ans;        
    }
};

The space requirement is constant and the time complexity is O(R – L) because counting the bits and checking if the number has prime-bits are constant.

How to Count the Prime Set Bits in Java using Integer.bitCount?

In Java, we can leverage the power of Integer.bitCount() so the code is quite similar to above C++ code.

1
2
3
4
5
6
7
8
9
10
11

class Solution {
    public int countPrimeSetBits(int L, int R) {
        int ans = 0;
        for (int x = L; x <= R; ++ x) {
            int bc = Integer.bitCount(x);
            if (bc == 2 || bc == 3 || bc == 5 || bc == 7 ||
                bc == 11 || bc == 13 || bc == 17 || bc == 19) ans ++;
        }
        return ans;
    }
}

class Solution {
    public int countPrimeSetBits(int L, int R) {
        int ans = 0;
        for (int x = L; x <= R; ++ x) {
            int bc = Integer.bitCount(x);
            if (bc == 2 || bc == 3 || bc == 5 || bc == 7 ||
                bc == 11 || bc == 13 || bc == 17 || bc == 19) ans ++;
        }
        return ans;
    }
}

Counting Prime Set Bits in Python

We can use bin to convert an integer to binary string in Python, then we can count the occurrences of Ones in the string.

1
2
3
4
5
6
7
8
9

class Solution:
    def countPrimeSetBits(self, L: int, R: int) -> int:
        ans = 0
        primes = [2, 3, 5, 7, 11, 13, 17, 19]
        for i in range(L, R + 1):
            bc = bin(i).count('1')
            if bc in primes:
                ans += 1
        return ans

class Solution:
    def countPrimeSetBits(self, L: int, R: int) -> int:
        ans = 0
        primes = [2, 3, 5, 7, 11, 13, 17, 19]
        for i in range(L, R + 1):
            bc = bin(i).count('1')
            if bc in primes:
                ans += 1
        return ans

However, the above Python is slow i.e. the in operator that checks if an element appears in a list/array in Python is O(N) time.

–EOF (The Ultimate Computing & Technology Blog) —