Prime number of set bits in binary representation
July 21, 2022
math-and-geometryProblem URL: Prime number of set bits in binary representation
We will create 2 helper function, one for checking the prime number, another for counting the number of 1 bits. Then we iterate over the range, then count the number of bits, and then check whether the bit count is prime or not. If the bit count is prime we increate our result and finally return it after the iteration is over.
class Solution:
def countPrimeSetBits(self, left: int, right: int) -> int:
count = 0
for num in range(left, right+1):
bits = self.countBits(num)
if self.isPrime(bits) == True:
count += 1
return count
def isPrime(self, num: int) -> bool:
if num < 2: return False
if num == 2: return True
if num % 2 == 0: return False
for i in range(3, floor(sqrt(num))+1, 2):
if num % i == 0:
return False
return True
def countBits(self, num: int) -> int:
count = 0
while num:
count += num & 1
num >>= 1
return count
Time Complexity: O(n^2)
Space Complexity: O(1)