Prime Number of Set Bits in Binary Representation

We can define a helper function is_prime to check if a number is prime.

To solve this problem, we need to iterate over the range from left to right (inclusive). For each number, we convert it to binary and count the set bits. Then we use the is_prime function to check if the number of set bits is a prime number. We increment the counter if it is.

Here is the Python code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        def is_prime(n: int) -> bool:
            if n < 2:
                return False
            for i in range(2, int(n ** 0.5) + 1):
                if n % i == 0:
                    return False
            return True

        counter = 0
        for num in range(left, right + 1):
            set_bits = bin(num).count('1')
            if is_prime(set_bits):
                counter += 1

        return counter

The function bin(x) converts an integer number to a binary string. The count('1') function then counts the number of ‘1’ characters in the string, which corresponds to the number of set bits in the binary representation of the number.

Q&A

why my code is not running for long value such as 3 digit number range…..

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
  public: bool isPrime(long int n) {
    if (n == 1)
      return false;
    if (n == 2 || n == 3)
      return true;
    if (n % 2 == 0 || n % 3 == 0)
      return false;
    for (long int i = 5; i < n; i = i + 6)
      if (n % i == 0 || n % (i + 2) == 0)
        return false;
    return true;
  }
  int count(long int x) {
    int c = 0;
    while (x != 0) {
      x = x & (x - 1);
      c++;
    }
    return c;
  }
  int countPrimeSetBits(int left, int right) {
    int c = 0;
    for (long int i = left; i <= right; i++) {
      if (isPrime(count(i)) == 1)
        c++;
    }
    return c;
  }
};

Your original C++ code is generally correct in logic, but it can be optimized in terms of efficiency.

The isPrime function, as it’s currently written, iterates over every number from 2 to n to check whether n is divisible by any of these numbers. This is not efficient for larger n because it requires a lot of division operations. A more efficient approach is to check divisibility only up to the square root of n, because a larger factor of n would have a corresponding smaller factor that has already been tested.

Your count function also has room for optimization. This function is using the Brian Kernighan’s Algorithm to count the set bits in an integer. It’s generally an efficient way to count set bits, but when you know your input range, you can limit the calculations that you need to perform.

In your specific problem, you’re working with 32-bit integers. Therefore, the maximum number of set bits in a number would be 32. But, since you only have to find the count of prime set bits, and the largest prime number less than 32 is 31, you only have to check for primes numbers up to 31. This can significantly reduce the number of iterations in your isPrime function.

Here’s an optimized version of your C++ code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    bool isPrime(int n) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        for (int i = 5; i * i <= n; i += 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
        return true;
    }

    int countSetBits(int n) {
        int count = 0;
        while (n) {
            n &= (n - 1);
            count++;
        }
        return count;
    }

    int countPrimeSetBits(int left, int right) {
        int count = 0;
        for (int i = left; i <= right; i++) {
            if (isPrime(countSetBits(i))) count++;
        }
        return count;
    }
};

This version of the code reduces the range of numbers checked in the isPrime function to only up to the square root of n, and keeps the countSetBits function the same. The main function countPrimeSetBits remains the same. This optimized version should run faster, especially for larger input ranges.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        primes = {2, 3, 5, 7, 11, 13, 17, 19}
        c = 0

        for i in range(left, right + 1):
            if i.bit_count() in primes:
                c += 1

        return c

Problem Classification

Problem Category: This problem falls under the category of ‘Computational Number Theory’ and ‘Bit Manipulation’.

‘What’ Components:

  1. Range of numbers: The problem statement provides a range of integers, denoted by ’left’ and ‘right’.
  2. Binary representation: The solution requires dealing with the binary representation of numbers.
  3. Set bits: It’s necessary to count the number of set bits (1’s) in the binary representation.
  4. Prime numbers: The count of set bits is to be evaluated for primality.
  5. Counting the required numbers: The task is to count all the numbers in the range that meet the condition.

Problem Classification:

  1. Computational Number Theory: The problem involves prime numbers, which are a fundamental concept in number theory.
  2. Bit Manipulation: The binary representation of numbers and the operation of counting set bits both fall under bit manipulation.

Explanation: The problem requires the application of number theory (specifically, primality checking) to the count of set bits in binary representations of numbers. Therefore, it can be classified as a computational number theory problem. In addition, it involves binary representation and operations on bits, making it a bit manipulation problem. The goal is to count the numbers in a given range that have a prime number of set bits.

Language Agnostic Coding Drills

  1. Dissecting the Code:

Concepts found in this code include:

a. Use of sets for storing unique elements: primes = {2, 3, 5, 7, 11, 13, 17, 19}

b. Use of loops to iterate over a range of numbers: for i in range(left, right + 1)

c. Use of bit operations to count the number of set bits in a number: i.bit_count()

d. Checking for membership in a set: if i.bit_count() in primes

e. Updating and returning a counter: c += 1 and return c

  1. Listing and Classifying the Concepts:

a. Use of sets for storing unique elements - Beginner: Basic knowledge of Python data structures.

b. Use of loops to iterate over a range of numbers - Beginner: Fundamental programming concept.

c. Updating and returning a counter - Beginner: Basic concept of incrementing a counter variable.

d. Checking for membership in a set - Intermediate: Involves the knowledge of set operations.

e. Use of bit operations to count the number of set bits in a number - Intermediate: Requires understanding of binary representation and bitwise operations.

  1. Problem-Solving Approach:

Start by initializing a set of small prime numbers (up to 19, which is the number of bits in the binary representation of 10^6, the maximum possible ‘right’ value). Next, initialize a counter variable to zero.

Then, iterate over the inclusive range from ’left’ to ‘right’. For each number, count the number of set bits in its binary representation. If this count is in the prime set, increment the counter.

By iterating over all the numbers in the range, this approach ensures that all numbers with a prime number of set bits are counted. The use of the set makes the membership test efficient, as checking whether an element is in a set in Python takes constant time on average.

Finally, return the counter, which represents the total count of numbers in the range that have a prime number of set bits in their binary representation.

Each concept or drill plays a crucial role in the overall solution, contributing to either the iteration over the range, the calculation of the set bits, the prime check, or the count update.

Targeted Drills in Python

  1. Python-Based Coding Drills:

a. Use of sets for storing unique elements:

1
2

primes = {2, 3, 5, 7, 11, 13, 17, 19}
print(primes)

b. Use of loops to iterate over a range of numbers:

1
2

for i in range(1, 11):
    print(i)

c. Updating and returning a counter:

1
2
3
4

counter = 0
for i in range(1, 11):
    counter += 1
print(counter)

d. Checking for membership in a set:

1
2
3

primes = {2, 3, 5, 7, 11, 13, 17, 19}
if 7 in primes:
    print("7 is a prime number")

e. Use of bit operations to count the number of set bits in a number:

1
2
3

num = 21
num_of_set_bits = bin(num).count('1')
print(num_of_set_bits)
  1. Problem-Specific Concepts:

The main problem-specific concept in this code is counting the number of set bits in an integer, and checking whether this count is prime. This concept is essential for our problem because the problem specifically asks us to count the numbers in a range that have a prime number of set bits in their binary representation.

  1. Integrating the Drills:

Start by initializing a set of small prime numbers (concept a). Also, initialize a counter to zero (concept c). Then, iterate over the inclusive range from ’left’ to ‘right’ (concept b). For each number, count the number of set bits in its binary representation (concept e). If this count is in the prime set, increment the counter (concept c and d). Finally, return the counter (concept c).

All of these concepts contribute to the final solution, and they can be assembled in this order to solve the initial problem.