762. Prime Number of Set Bits in Binary Representation

EasyBit ManipulationMath
Leetcode Link

Problem Description

The problem provides us with two integers, left and right, and asks us to calculate how many numbers in the range from left to right (inclusive) have a prime number of set bits in their binary representations. The term "set bits" refers to the number of 1’s that appear in the binary form of a given number. For example, the number 21 has a binary representation of 10101, which contains three 1’s, or three set bits.

Intuition

The intuition behind the solution can be broken down into a few logical steps:

  1. Identify the Prime Numbers: Since we are interested in numbers that have a prime number of set bits, we first need a set of prime numbers to check against. However, we don't need all prime numbers, just the ones within the possible range of set bits for numbers in our input range. Given that the max value for a 32-bit integer is 2^31 - 1, it has at maximum 31 set bits. The prime numbers within this range are {2, 3, 5, 7, 11, 13, 17, 19}.

  2. Count Set Bits: For each number in the inclusive range between left and right, we need to determine the number of set bits. There is a built-in method in Python called bit_count for integers that do just that, counting the number of bits set to 1 in binary representation.

  3. Check Primes: Once we have the count of set bits for a number, we check if this count is in our pre-identified set of prime numbers.

  4. Summing Up Prime Set Bits Counts: Finally, we need to sum up how many numbers fall within our criteria. This is done using sum comprehension in Python, where for each number in our range, we count it only if the number of set bits is a prime number.

By combining these steps, we are able to arrive at the final count efficiently.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following shows the order of node visit in a Breadth-first Search?

Solution Approach

The implementation of the solution uses a simple but effective approach:

  1. Define a Set of Prime Numbers:

    • We create a set called primes which contains the prime numbers less than 20 (as calculated above, since 32-bit integers have a maximum of 31 set bits, and 19 is the largest prime number less than 31).
    • The set data structure is chosen due to its O(1) time complexity for membership checking, as we will need to check if a count (number of set bits) is a prime number.

  2. Iterate Over the Range:

    • We loop over each number from left to right (inclusive) using a range in the loop: for i in range(left, right + 1).
    • This iteration is simple and direct, covering each integer in the provided range.

  3. Count the Set Bits:

    • For each number i in the range, we use the bit_count() method to find the number of set bits for that number.
    • The use of bit_count() is a Python-specific method introduced in version 3.10 which simplifies and optimizes the operation of counting set bits.

  4. Check for Prime Number of Set Bits:

    • The comprehension part i.bit_count() in primes checks if the number of set bits is in our set of prime numbers.
    • If the number of set bits is a prime number, this evaluates to True, which, when summed using the sum() function, is treated as 1.

  5. Calculate the Total Count:

    • Finally, the sum() function adds up all the 1s (for each True result) reflecting the count of numbers that satisfy the condition (having a prime number of set bits).

The entire operation returns the sum, which is precisely the count of numbers with a prime number of set bits in the specified range. This approach is efficient because it minimizes the calls to check for prime numbers by predefining the possible primes and uses bitwise operation optimized functions for count calculation.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Example Walkthrough

Let's take the range from left = 10 to right = 15 and illustrate the solution approach step by step.

  1. Define the Set of Prime Numbers: We have a pre-determined set of prime numbers, which are {2, 3, 5, 7, 11, 13, 17, 19} because we are working within the 32-bit integer range.

  2. Iterate Over the Range: We review the numbers 10, 11, 12, 13, 14, and 15.

  3. Count the Set Bits and Check for Prime Number of Set Bits:

    • For the number 10 which in binary is 1010, there are two set bits. Two is a prime number.
    • For the number 11 which in binary is 1011, there are three set bits. Three is also a prime number.
    • For the number 12 which in binary is 1100, there are two set bits. Two is a prime number.
    • For the number 13 which in binary is 1101, there are three set bits. Three is a prime number.
    • For the number 14 which in binary is 1110, there are three set bits. Three is a prime number.
    • For the number 15 which in binary is 1111, there are four set bits. Four is not a prime number.

  4. Calculate the Total Count: Out of the numbers from 10 to 15:

    • Four numbers (10, 11, 12, 13, 14) have a prime number of set bits.
    • Two numbers (15) do not.

Therefore, the final count of numbers with a prime number of set bits between 10 and 15, inclusive, is 4.

Solution Implementation

1class Solution:
2    def count_prime_set_bits(self, left: int, right: int) -> int:
3        # Define a set of prime numbers that could represent set bit counts
4        primes = {2, 3, 5, 7, 11, 13, 17, 19}
5
6        # Use list comprehension to count the number of integers in the specified range
7        # which have a prime number of set bits (1s in their binary representation)
8        prime_set_bits_count = sum(
9            bin(i).count('1') in primes
10            for i in range(left, right + 1)
11        )
12
13        return prime_set_bits_count
14
1import java.util.Set;
2
3class Solution {
4    // Initialization of a Set containing prime numbers.
5    private static final Set<Integer> PRIME_NUMBERS = Set.of(2, 3, 5, 7, 11, 13, 17, 19);
6
7    // Method to count the numbers in the given range with a prime number of set bits.
8    public int countPrimeSetBits(int left, int right) {
9        // Initialize a counter for the numbers meeting the criteria.
10        int primeSetBitsCount = 0;
11      
12        // Iterate over the range from left to right, inclusive.
13        for (int i = left; i <= right; ++i) {
14            // Use Integer.bitCount to determine the number of set bits in the binary representation of 'i'.
15            // If the number of set bits is in the PRIME_NUMBERS set, increment the counter.
16            if (PRIME_NUMBERS.contains(Integer.bitCount(i))) {
17                primeSetBitsCount++;
18            }
19        }
20      
21        // Return the total count of numbers with a prime number of set bits.
22        return primeSetBitsCount;
23    }
24}
25
1#include <unordered_set>
2
3class Solution {
4public:
5    // Function to count the number of integers within a range [left, right] 
6    // that have a prime number of set bits in their binary representation
7    int countPrimeSetBits(int left, int right) {
8        // Define a set of primes that are less than or equal to 19, since the maximum
9        // number of bits for an int (32 bits) has at most 19 set bits to be a prime.
10        std::unordered_set<int> primeSet{2, 3, 5, 7, 11, 13, 17, 19};
11      
12        int count = 0; // This variable will store the count of numbers satisfying the condition
13      
14        // Iterate over each number in the given range
15        for (int i = left; i <= right; ++i) {
16            // Use __builtin_popcount to count the number of set bits in the current number
17            // Increase the count if the number of set bits is in the primeSet
18            count += primeSet.count(__builtin_popcount(i));
19        }
20      
21        // Return the final count
22        return count;
23    }
24};
25
1// Define a set of prime numbers less than or equal to 19
2const primeSet: Set<number> = new Set([2, 3, 5, 7, 11, 13, 17, 19]);
3
4// Function to count the number of integers within a range [left, right]
5// that have a prime number of set bits in their binary representation.
6function countPrimeSetBits(left: number, right: number): number {
7    let count = 0; // Initialize count of numbers satisfying the condition
8
9    // Iterate over each number within the range from left to right inclusive
10    for (let i = left; i <= right; i++) {
11        // Count the number of set bits (1s) in the binary representation of the number
12        const setBits = countSetBits(i);
13
14        // If the number of set bits is prime, increment the count
15        if (primeSet.has(setBits)) {
16            count++;
17        }
18    }
19
20    // Return the final count
21    return count;
22}
23
24// Helper function to count the number of set bits in the binary representation of a number
25function countSetBits(num: number): number {
26    let setBits = 0; // Initialize count of set bits to 0
27
28    while (num > 0) {
29        setBits += num & 1; // Increment setBits if the least significant bit is 1
30        num >>= 1; // Right shift the number to check the next bit
31    }
32
33    return setBits;
34}
35
Not Sure What to Study? Take the 2-min Quiz：

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Time and Space Complexity

Time Complexity

The time complexity of the given code is mainly determined by the for loop, which iterates from left to right inclusive.

We let N represent the number of integers in the range [left, right], then N equals right - left + 1.

For each i in the range [left, right], we calculate the number of set bits using i.bit_count(). Since the maximum number of bits for an integer is bounded by the logarithm of the integer, let's denote the number of bits as k. The operation bit_count() has a time complexity of O(k).

However, since the values of left and right are not restricted by input size as in traditional algorithm analyses, where N would normally depend on some input parameter like array size, defining k is trickier. Generally, for a 32-bit integer, k would be at most 32. Thus we can consider bit_count() operation to be O(1) for practical purposes.

Therefore, since bit_count() takes constant time and is called N times, the time complexity of the entire loop is O(N).

The set membership test in primes is O(1) because lookup in a set of prime numbers (of fixed small size) is constant time.

Combining these, the loop has a time complexity of O(N * 1) = O(N).

Space Complexity

The space complexity of the given code is low.

We have a set, primes, containing a fixed number of prime numbers which is independent of the input size. This means it consumes a constant amount of space, O(1).

The temporary variables for the loop and the sum operation are also constant space, so they do not contribute to the space complexity in terms of N.

Therefore, the overall space complexity of the code is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫