Prime Number of Set Bits in Binary Representation
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,
21written in binary is10101, which has3set bits.
Example 1
Input
left = 6, right = 10Output
4The numbers 6, 7, 9, and 10 have a prime number of set bits, so the count is 4.
Example 2
Input
left = 10, right = 15Output
5The numbers 10, 11, 12, 13, and 14 have a prime number of set bits, so the count is 5.
Constraints
- 1 <= left <= right <= 10^6
- 0 <= right - left <= 10^4