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

## Description

https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/

Given two integers `left` and `right`, find the count of numbers in the range `[left, right]` (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 `1`s 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: left = 6, right = 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: left = 10, right = 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:

1. `left, right` will be integers `left <= right` in the range `[1, 10^6]`.
2. `right - left` will be at most 10000.

## Explanation

Convert integer to bits and count how many bits are there. And then check if the count of bits is a prime number

## Python Solution

``````class Solution:
def countPrimeSetBits(self, L: int, R: int) -> int:
count = 0

for i in range(L, R + 1):
bin_i = bin(i)[2:]
count_bits = bin_i.count('1')

if count_bits > 1 and self.is_prime(count_bits):
count += 1

return count

def is_prime(self, n):
for i in range(2, floor(sqrt(n)) + 1):
if n % i == 0:
return False

return True``````
• Time Complexity: O(N^2).
• Space Complexity: O(N).