# LeetCode 762: Prime Number of Set Bits in Binary Representation

## Problem Restatement

We are given two integers:

```python
left
right
```

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

```python
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:

```text
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:

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

## Examples

Example 1:

```python
left = 6
right = 10
```

Output:

```python
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:

```python
left = 10
right = 15
```

Output:

```python
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:

```python
bin(21)
```

returns:

```python
"0b10101"
```

Then:

```python
bin(21).count("1")
```

returns:

```python
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:

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

Then for each number:

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

## Counting Set Bits

Python provides:

```python
x.bit_count()
```

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

Examples:

```python
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:

```text
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

```python
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:

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

The answer starts at zero:

```python
answer = 0
```

Then we scan the full inclusive range:

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

For every number, we count the set bits:

```python
x.bit_count()
```

If that count is prime, we include the number:

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

Finally:

```python
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.

```python
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:

```python
y & 1
```

checks whether the last bit is `1`.

Then:

```python
y >>= 1
```

removes the last bit.

## Testing

```python
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 |