Prime Number of Set Bits in Binary Representation

Easy

Asked by:

12 views

Topics:

Bit Manipulation

Given two integers left and right, return the count of numbers in the inclusive range [left, right] having a prime number of set bits in their binary representation.

Recall that the number of set bits an integer has is the number of 1's present when written in binary.

For example, 21 written in binary is 10101, which has 3 set bits.

Example 1:

Input: left = 6, right = 10
Output: 4
Explanation:
6  -> 110 (2 set bits, 2 is prime)
7  -> 111 (3 set bits, 3 is prime)
8  -> 1000 (1 set bit, 1 is not prime)
9  -> 1001 (2 set bits, 2 is prime)
10 -> 1010 (2 set bits, 2 is prime)
4 numbers have a prime number of set bits.

Example 2:

Input: left = 10, right = 15
Output: 5
Explanation:
10 -> 1010 (2 set bits, 2 is prime)
11 -> 1011 (3 set bits, 3 is prime)
12 -> 1100 (2 set bits, 2 is prime)
13 -> 1101 (3 set bits, 3 is prime)
14 -> 1110 (3 set bits, 3 is prime)
15 -> 1111 (4 set bits, 4 is not prime)
5 numbers have a prime number of set bits.

Constraints:

1 <= left <= right <= 10⁶
0 <= right - left <= 10⁴

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of the input values left and right? Are they non-negative?
Do we need to handle any potential integer overflow issues during the bit counting process?
Is the range `[left, right]` inclusive of both `left` and `right`?
What should be returned if `left` is greater than `right`?
By 'prime,' do you mean a number only divisible by 1 and itself, excluding 1 itself?

Brute Force Solution

Approach

The brute force approach to this problem involves examining every number within a given range. For each number, we determine if the count of '1' bits in its binary form is a prime number, and then count how many times this happens.

Here's how the algorithm would work step-by-step:

Take the first number from the starting point of your range.
Figure out the binary representation of that number (convert it to binary).
Count how many '1's are in that binary representation.
Check if that count is a prime number (a number only divisible by 1 and itself).
If the count is prime, add one to your running total.
Repeat the process for the next number in your range, and keep doing this until you get to the end of the range.
The final total is your answer.

Code Implementation

def prime_number_of_set_bits(left, right):
    number_of_primes = 0

    for number in range(left, right + 1):
        binary_representation = bin(number)[2:]
        set_bits_count = binary_representation.count('1')

        # Check if the number of set bits is prime
        if set_bits_count > 1:

            is_prime = True

            # Optimization: only need to check up to the square root
            for i in range(2, int(set_bits_count**0.5) + 1):

                if set_bits_count % i == 0:
                    is_prime = False
                    break

            # Only increment if number of set bits is indeed prime
            if is_prime:
                number_of_primes += 1

    return number_of_primes

Big(O) Analysis

Time Complexity

O(R * log(R)) – We iterate through a range of numbers from L to R, which has a size of R (where R > L, so R dominates). For each number, we count the set bits, which takes O(log(R)) time since the number of bits needed to represent R grows logarithmically. The primality test for the count of set bits takes a roughly constant amount of time, but we can still represent the complexity as O(log(R)) (or O(sqrt(log(R))) if we used a more efficient primality test, but log(R) will dominate). Therefore the overall time complexity is O(R * log(R)).

Space Complexity

O(1) – The provided brute force approach iterates through a range of numbers, performing bit counting and primality tests on each. While the algorithm iterates, it does not allocate significant auxiliary data structures that scale with the input range (N, where N is the difference between the range's start and end). Temporary variables may be used for bit counting and primality tests, but their space requirement remains constant regardless of the range size. Therefore, the space complexity is O(1), indicating constant extra space usage.

Optimal Solution

Approach

The problem requires us to count numbers within a range where the number of '1's in their binary form is a prime number. The most efficient approach involves directly counting the '1's in the binary representation of each number and checking if that count is a prime number using a precomputed list.

Here's how the algorithm would work step-by-step:

First, create a small list of prime numbers since the maximum number of set bits will be limited by the size of the largest number we are checking.
Go through each number in the given range one by one.
For each number, figure out how many '1's are in its binary representation.
Check if the count of '1's that you found is included in your list of precomputed prime numbers.
If it is, increase the count. If not, move on to the next number.
After you have gone through all the numbers in the range, the final count will be your answer.

Code Implementation

def prime_number_of_set_bits_in_binary_representation(left, right):
    prime_numbers = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}
    count = 0

    for number in range(left, right + 1):
        # Count the number of set bits
        set_bits_count = bin(number).count('1')

        # Check if the count of set bits is a prime number
        if set_bits_count in prime_numbers:

            # Increment the total count
            count += 1

    return count

Big(O) Analysis

Time Complexity

O(R) – The solution iterates through a range of numbers from L to R, where the difference R-L drives the execution time which we can represent as R. For each number, it counts the set bits, which takes O(log(R)) time in the worst case (proportional to the number of bits). However, since the maximum number of set bits is bounded and checking primality is a constant time operation using a precomputed list, the primality test does not affect the time complexity. Therefore, the dominant operation is iterating through each number in the range. Hence, the time complexity is approximately O(R).

Space Complexity

O(1) – The algorithm uses a precomputed list of prime numbers. The size of this list is constant because the maximum possible number of set bits is limited by the problem's constraints, meaning it doesn't scale with the input range (left and right). The algorithm also uses a few integer variables for counting and iteration, which take up constant space. Therefore, the auxiliary space used is independent of the input range size.

Edge Cases

Case	How to Handle
Low bound is 0	The problem should explicitly state whether zero should be included in the range or not; assume it's inclusive and count the bits of zero appropriately.
High bound is a very large number (close to integer limit)	Check for potential integer overflow issues when counting set bits for large numbers, especially if using bitwise operations without considering the sign bit.
Low bound is equal to the high bound	If low equals high, check if the number of set bits in its binary representation is prime, and return a list containing 1 if it is, otherwise 0.
Low bound is negative	Clarify with the interviewer about handling negative numbers since the number of set bits in a negative number's two's complement representation can be different.
Large interval between low and high	Consider optimizing the bit counting function for speed, as the function might be called many times; precompute primes within a certain range.
Interval contains only even numbers	Test how the prime set bit count behaves when many numbers have even parity (might affect overall performance).
Interval contains only powers of 2	Powers of two have exactly one set bit, so count the number of powers of two in the interval and check if 1 is prime (it isn't).
Integer overflow in calculating number of set bits	Ensure intermediate results when calculating set bits (especially using bitwise operators and shifts on potentially large values) do not lead to integer overflow, using appropriate data types.

Low bound is 0

How to Handle:

The problem should explicitly state whether zero should be included in the range or not; assume it's inclusive and count the bits of zero appropriately.

High bound is a very large number (close to integer limit)

How to Handle:

Check for potential integer overflow issues when counting set bits for large numbers, especially if using bitwise operations without considering the sign bit.

Low bound is equal to the high bound

How to Handle:

If low equals high, check if the number of set bits in its binary representation is prime, and return a list containing 1 if it is, otherwise 0.

Low bound is negative

How to Handle:

Clarify with the interviewer about handling negative numbers since the number of set bits in a negative number's two's complement representation can be different.

Large interval between low and high

How to Handle:

Consider optimizing the bit counting function for speed, as the function might be called many times; precompute primes within a certain range.

Interval contains only even numbers

How to Handle:

Test how the prime set bit count behaves when many numbers have even parity (might affect overall performance).

Interval contains only powers of 2

How to Handle:

Powers of two have exactly one set bit, so count the number of powers of two in the interval and check if 1 is prime (it isn't).

Integer overflow in calculating number of set bits

How to Handle:

Ensure intermediate results when calculating set bits (especially using bitwise operators and shifts on potentially large values) do not lead to integer overflow, using appropriate data types.