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 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 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
The most straightforward approach is to iterate through each number in the given range [left, right]
, calculate the number of set bits (1s) in its binary representation, and then check if that count is a prime number. If it is, we increment our counter.
left
to right
(inclusive).def count_prime_set_bits_brute_force(left: int, right: int) -> int:
def count_set_bits(n: int) -> int:
count = 0
while n > 0:
n &= (n - 1)
count += 1
return count
def is_prime(n: int) -> bool:
if n <= 1:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
count = 0
for i in range(left, right + 1):
set_bits = count_set_bits(i)
if is_prime(set_bits):
count += 1
return count
right - left
is the range of numbers, log(right)
is the time to count set bits, and sqrt(log(right))
is the time to check for primality (since the maximum number of set bits will be log(right)).We can optimize the primality check by pre-calculating a set of prime numbers up to the maximum possible number of set bits (which is the number of bits in the binary representation of right
). Since right <= 10^6
, the maximum number of set bits is at most 20. We can create a set of primes and then simply check if the number of set bits is present in our prime set. Also instead of computing square root for each is_prime call we can precompute the primes upto 20 since max number of bits is 20.
left
to right
(inclusive).def count_prime_set_bits_optimized(left: int, right: int) -> int:
def count_set_bits(n: int) -> int:
count = 0
while n > 0:
n &= (n - 1)
count += 1
return count
primes = {2, 3, 5, 7, 11, 13, 17, 19}
count = 0
for i in range(left, right + 1):
set_bits = count_set_bits(i)
if set_bits in primes:
count += 1
return count
left
or right
are negative, the bit counting logic might have to be changed depending on the language.left > right
, then the for loop will not run, so return 0.