Prime Number of Set Bits in Binary Representation

Problem

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, 21 written in binary is 10101, which has 3 set bits.

Constraints

• 1 <= left <= right <= 106
• 0 <= right - left <= 104

Solution

The problem Prime Number of Set Bits in Binary Representation can be solved by iterating through the given range and checking if each numbers has a prime number of set bits. Since numbers equal to or less than 10⁶ can have maximum of 19 bits set, we only need to compare the number of set bits to the prime numbers equal to or less than 19.

Implementation

static const int fast_io = []()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

class Solution
{
  public:
    int countPrimeSetBits(int left, int right)
    {
        int count = 0;
        do
        {
            bitset<20> bits(left);
            switch (bits.count())
            {
            case 2:
            case 3:
            case 5:
            case 7:
            case 11:
            case 13:
            case 17:
            case 19:
                count += 1;
            }
        } while (++left <= right);

        return count;
    }
};