LeetCode 762: Prime Number of Set Bits in Binary Representation

Problem Restatement

We are given two integers:

left
right

We need to count how many integers x in the inclusive range:

left <= x <= right

have a prime number of set bits in their binary representation.

A set bit is a bit equal to 1.

For example:

21 = 10101

The binary representation of 21 has three 1 bits.

Since 3 is prime, 21 should be counted.

Also, 1 is not prime.

Input and Output

Example function shape:

def countPrimeSetBits(left: int, right: int) -> int:
    ...

Examples

Example 1:

left = 6
right = 10

Output:

4

Check every number:

So the answer is 4.

Example 2:

left = 10
right = 15

Output:

5

Check every number:

So the answer is 5.

First Thought: Convert to Binary String

A simple way is to convert each number to binary and count the number of 1 characters.

For example:

bin(21)

returns:

"0b10101"

Then:

bin(21).count("1")

returns:

3

This is easy to understand and works.

But Python also has a direct method for counting set bits.

Key Insight

The range length is limited, so we can check every number from left to right.

For each number, we only need two operations:

1. Count its set bits.
2. Check whether that count is prime.

Since right <= 10^6, the binary representation has fewer than 20 bits.

So the possible set-bit counts are small.

The only prime counts we need are:

{2, 3, 5, 7, 11, 13, 17, 19}

Then for each number:

if x.bit_count() in primes:
    answer += 1

Counting Set Bits

Python provides:

x.bit_count()

This returns the number of 1 bits in the binary representation of x.

Examples:

6.bit_count()   # 2, because 6 is 110
7.bit_count()   # 3, because 7 is 111
8.bit_count()   # 1, because 8 is 1000

Algorithm

1. Store the prime set-bit counts in a set.
2. Initialize answer = 0.
3. Loop through every number x from left to right.
4. Count the set bits of x.
5. If the count is prime, increment answer.
6. Return answer.

Correctness

The algorithm checks every integer in the range [left, right] exactly once.

For each integer x, x.bit_count() gives the number of 1 bits in its binary representation.

The set primes contains exactly the prime numbers that can occur as set-bit counts under the constraints.

If x.bit_count() is in primes, then x has a prime number of set bits, so the algorithm counts it.

If x.bit_count() is not in primes, then x does not have a prime number of set bits, so the algorithm does not count it.

Therefore, the final answer is exactly the number of integers in [left, right] whose binary representation has a prime number of set bits.

Complexity

Let:

n = right - left + 1

Implementation

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        primes = {2, 3, 5, 7, 11, 13, 17, 19}
        answer = 0

        for x in range(left, right + 1):
            if x.bit_count() in primes:
                answer += 1

        return answer

Code Explanation

We first store all possible prime set-bit counts:

primes = {2, 3, 5, 7, 11, 13, 17, 19}

The answer starts at zero:

answer = 0

Then we scan the full inclusive range:

for x in range(left, right + 1):

For every number, we count the set bits:

x.bit_count()

If that count is prime, we include the number:

if x.bit_count() in primes:
    answer += 1

Finally:

return answer

returns the total count.

Alternative Without bit_count

Some older Python versions may not support int.bit_count().

In that case, we can count bits manually.

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        primes = {2, 3, 5, 7, 11, 13, 17, 19}
        answer = 0

        for x in range(left, right + 1):
            count = 0
            y = x

            while y > 0:
                count += y & 1
                y >>= 1

            if count in primes:
                answer += 1

        return answer

The expression:

y & 1

checks whether the last bit is 1.

Then:

y >>= 1

removes the last bit.

Testing

def run_tests():
    s = Solution()

    assert s.countPrimeSetBits(6, 10) == 4
    assert s.countPrimeSetBits(10, 15) == 5
    assert s.countPrimeSetBits(1, 1) == 0
    assert s.countPrimeSetBits(2, 2) == 1
    assert s.countPrimeSetBits(1, 2) == 1
    assert s.countPrimeSetBits(16, 16) == 0

    print("all tests passed")

run_tests()

Test meaning: