LeetCode 762: Prime Number of Set Bits in Binary Representation

A clear explanation of counting numbers whose binary representation has a prime number of set bits.

leetcodebit-manipulationmath

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

Item Meaning
Input Two integers left and right
Range All integers from left to right, inclusive
Output Count of numbers whose set-bit count is prime

Example function shape:

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

Examples

Example 1:

left = 6
right = 10

Output:

4

Check every number:

Number Binary Set Bits Prime?
6 110 2 Yes
7 111 3 Yes
8 1000 1 No
9 1001 2 Yes
10 1010 2 Yes

So the answer is 4.

Example 2:

left = 10
right = 15

Output:

5

Check every number:

Number Binary Set Bits Prime?
10 1010 2 Yes
11 1011 3 Yes
12 1100 2 Yes
13 1101 3 Yes
14 1110 3 Yes
15 1111 4 No

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
Metric Value Why
Time O(n) We check each number once
Space O(1) The prime set has fixed size

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:

Test Why
[6, 10] Main example
[10, 15] Main example with six numbers
[1, 1] One set bit is not prime
[2, 2] 2 is binary 10, one set bit, but wait carefully: not prime
[1, 2] Both numbers have one set bit, so answer should be 0
[16, 16] Power of two has one set bit