#762
Prime Number of Set Bits in Binary Representation
newbie · 235 · lc easy +18 · verified · 78.7% accepted · 1,027 likes · top 90%
Description
Given integers left and right, count how many numbers in the inclusive range [left, right] have a prime number of set bits (i.e., 1-bits) in their binary representation. For instance, 21 in binary is 10101, which has 3 set bits, and 3 is 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)
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.
Code
1
2
3