Welcome to Subscribe On Youtube
762. Prime Number of Set Bits in Binary Representation
Description
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 is10101
, which has3
set bits.
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) 8 > 1000 (1 set bit, 1 is not prime) 9 > 1001 (2 set bits, 2 is prime) 10 > 1010 (2 set bits, 2 is prime) 4 numbers have a prime number of set bits.
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) 5 numbers have a prime number of set bits.
Constraints:
1 <= left <= right <= 10^{6}
0 <= right  left <= 10^{4}
Solutions

class Solution { private static Set<Integer> primes = Set.of(2, 3, 5, 7, 11, 13, 17, 19); public int countPrimeSetBits(int left, int right) { int ans = 0; for (int i = left; i <= right; ++i) { if (primes.contains(Integer.bitCount(i))) { ++ans; } } return ans; } }

class Solution { public: int countPrimeSetBits(int left, int right) { unordered_set<int> primes{2, 3, 5, 7, 11, 13, 17, 19}; int ans = 0; for (int i = left; i <= right; ++i) ans += primes.count(__builtin_popcount(i)); return ans; } };

class Solution: def countPrimeSetBits(self, left: int, right: int) > int: primes = {2, 3, 5, 7, 11, 13, 17, 19} return sum(i.bit_count() in primes for i in range(left, right + 1))

func countPrimeSetBits(left int, right int) (ans int) { primes := map[int]int{} for _, v := range []int{2, 3, 5, 7, 11, 13, 17, 19} { primes[v] = 1 } for i := left; i <= right; i++ { ans += primes[bits.OnesCount(uint(i))] } return }