Prime Number Of Set Bits In Binary Representation - Leetcode Solution

The problem "Prime Number Of Set Bits In Binary Representation" on LeetCode asks us to count the number of prime numbers in the binary representation of a range of numbers. We are given two integers L and R, and we need to find the count of all the prime numbers that occur in the range of binary representation of numbers from L to R inclusive.

To solve this problem, we can use the following steps:

Step 1: Create a helper function to check if a number is prime

We can create a helper function is_prime(x) to check if a number x is prime. We can use the standard algorithm to check for prime numbers, which is to check if x is divisible by any number from 2 to sqrt(x). If x is divisible by any number in this range, it is not prime, otherwise it is prime.

Step 2: Loop through the range from L to R

We need to loop through the range of numbers from L to R inclusive. For each number in this range, we need to convert it into binary and count the number of set bits (i.e., the number of 1's) in its binary representation.

Step 3: Check if the count of set bits is prime

After we have counted the number of set bits in the binary representation of a number, we need to check if this count is prime or not. We can use the helper function is_prime(x) to check if the count is prime or not.

Step 4: Increment the count if the count of set bits is prime

If the count of set bits in the binary representation of a number is prime, we need to increment the count of prime numbers we have found so far.

Step 5: Return the count of prime numbers

After we have looped through all the numbers in the range from L to R inclusive, we need to return the count of prime numbers we have found so far.

Here is the Python implementation of the solution:

class Solution(object):
    def countPrimeSetBits(self, L, R):
        """
        :type L: int
        :type R: int
        :rtype: int
        """
        def is_prime(x):
            if x <= 1:
                return False
            for i in range(2, int(x**0.5)+1):
                if x % i == 0:
                    return False
            return True
        
        count = 0
        for n in range(L, R+1):
            set_bits = bin(n).count('1')
            if is_prime(set_bits):
                count += 1
        
        return count

Time Complexity: O((R-L+1)log(R)), where log(R) is the length of the binary representation of R.

Space Complexity: O(1). We are only using constant extra space for storing the count of prime numbers.

1