Prime Number of Set Bits in Binary Representation

Easy

Given two integers left and right, provide the count of numbers in the inclusive range [left, right] having a prime count of set bits in their binary representation.

Recall that the count of set bits an integer has is the count of 1 's present when written in binary.

For example, 21 written in binary is 10101, which has 3 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 count 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 count of set bits.

Constraints

1 <= left <= right <= 10^6
0 <= right - left <= 10^4

Did this problem appear in one of your interviews?

Responses stay private.

Constraints

Did this problem appear in one of your interviews?

Acceptance rate: 0%