Leetcode – Prime Number of Set Bits in Binary Representation Solution in Python

Spread the love

In the world of competitive programming and coding challenges, problems that mix mathematical concepts with computational techniques are frequent. One such interesting problem is determining if the number of set bits (or 1s) in the binary representation of a number is prime. This problem, known as the “Prime Number of Set Bits in Binary Representation,” can be found on platforms like Leetcode.

In this article, we will dissect this problem, understand its intricacies, and provide a comprehensive solution in Python.

Problem Statement

Given two integers L and R, you need to find the count of numbers in the inclusive range [L, R] having a prime number of set bits in their binary representation.Note:

  • L, R will be integers in the range [1, 10^6].
  • L <= R.

Analysis

Before diving into the solution, let’s analyze the problem:

  1. The upper limit is 10^6, which in binary is a 20-bit number.
  2. The maximum number of set bits any number in this range can have is 20.
  3. We only need to consider prime numbers less than or equal to 20, which are: 2, 3, 5, 7, 11, 13, 17, 19.

Given this, our task boils down to finding how many numbers in the range [L, R] have a set bit count that is one of these prime numbers.

Python Solution

Brute Force Approach

A simple approach would be to check every number in the range [L, R], convert each to its binary form, count the set bits, and check if that count is prime.

However, since the range of the numbers can go up to 10^6, this method can be somewhat inefficient.

Optimized Approach

An optimized approach would involve precomputing the prime set bit counts and then just tallying numbers in the range [L, R] that match these counts.

Here’s a step-by-step breakdown:

  1. Precompute the set bit counts that are prime. As mentioned before, we only need to consider numbers with set bit counts of 2, 3, 5, 7, 11, 13, 17, 19.
  2. Loop through the range [L, R], count the set bits of each number using a helper function, and check if the count exists in our precomputed set.
  3. If it does, increment our result counter.

Here’s the Python code implementing this approach:

def countPrimeSetBits(L: int, R: int) -> int:
    
    def is_prime(n):
        """Helper function to check if a number is prime."""
        if n < 2:
            return False
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                return False
        return True

    # Precompute the set bit counts that are prime
    prime_counts = {i for i in range(20) if is_prime(i)}

    # Function to count set bits of a number
    count_bits = lambda x: bin(x).count('1')

    # Loop through the range [L, R], count set bits and check if the count is prime
    return sum(count_bits(i) in prime_counts for i in range(L, R + 1))

# Example Usage
L, R = 10, 15
print(countPrimeSetBits(L, R))  # Expected output: 5

Conclusion

The “Prime Number of Set Bits in Binary Representation” problem offers an intriguing mix of binary representation and prime number checking. While a brute force solution can work for smaller inputs, a more efficient solution is feasible by considering the problem’s constraints and properties. In coding challenges like these, understanding the inherent characteristics and limits of the problem can often guide us to a more efficient solution.

Leave a Reply