#762

Easy

LeetCode Problem Workspace

Prime Number of Set Bits in Binary Representation

Count numbers with prime set bits in a binary representation within a given range.

Problem Statement

You are given two integers, left and right, which define a range of integers [left, right]. Your task is to return the count of numbers in this range whose binary representation contains a prime number of set bits. A set bit is a '1' in the binary representation of a number, and a prime number is a positive integer greater than 1 that has no divisors other than 1 and itself.

For example, for the range [6, 10], the binary representations of the numbers are: 6 -> 110 (2 set bits), 7 -> 111 (3 set bits), 8 -> 1000 (1 set bit), 9 -> 1001 (2 set bits), and 10 -> 1010 (2 set bits). The numbers with a prime number of set bits are 6, 7, 9, and 10, so the result is 4.

Examples

Example 1

Input: left = 6, right = 10

Output: 4

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

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 <= 106
0 <= right - left <= 104

Solution Approach

Helper Function to Count Set Bits

Write a helper function that counts the number of set bits (1's) in the binary representation of a number. This can be achieved using bitwise operations like shifting and masking or by using built-in functions in some languages. This step is crucial as the problem revolves around the number of set bits.

Check for Prime Numbers

Once the number of set bits for a number is determined, check if that number is prime. You can either store a precomputed list of prime numbers or check for primality dynamically. The prime numbers relevant to this problem are the ones less than or equal to the maximum number of set bits, which is typically small.

Iterate Over the Range

Iterate through each number in the inclusive range [left, right], count the set bits, and check if the count is prime. Keep a running total of how many numbers have a prime number of set bits and return this count.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the method used for counting set bits and checking for primality. Counting set bits for a number can be done in O(log n) time, and checking primality takes O(√m), where m is the number of set bits. If iterating through all numbers in the range [left, right], the complexity is O(n log n) for n numbers, where n is the size of the range. Space complexity is O(1) if using constant space for counting set bits and prime checking.

What Interviewers Usually Probe

The candidate should focus on efficiently counting set bits and checking for primality.
A focus on optimization is important, especially with the constraint that the range length can be up to 10,000.
The candidate should ensure their solution handles the range limits appropriately and avoids unnecessary calculations.

Common Pitfalls or Variants

Common pitfalls

Incorrectly counting the number of set bits, leading to wrong results.
Inefficient primality testing, especially when checking large numbers repeatedly.
Overlooking edge cases like the smallest and largest numbers in the range.

Follow-up variants

Implement a solution using bit manipulation to count set bits.
Consider handling larger ranges more efficiently using precomputed prime numbers.
Optimize for cases where the difference between right and left is small, improving performance.

FAQ

How do I count set bits in a number?

You can count the set bits using bitwise operations, such as repeatedly shifting the number and applying a mask, or by using a built-in function like Python's bin(x).count('1').

What prime numbers should I check for?

You only need to check for prime numbers that are less than or equal to the maximum possible number of set bits. For most cases, these primes are 2, 3, 5, 7, 11, 13, 17, and a few others.

How can I optimize this solution for large ranges?

Precompute a list of prime numbers and use it to quickly check the primality of the set bit counts. Also, avoid redundant checks for numbers with the same number of set bits.

Can I use a built-in function to check primality?

Yes, many languages have built-in functions to check if a number is prime. You can also use libraries like math.isprime in Python.

What if the range size is very small?

For small ranges, a straightforward approach works fine. However, always keep efficiency in mind for larger ranges.

terminal

Solution

Solution 1: Math + Bit Manipulation

In the problem, both $\textit{left}$ and $\textit{right}$ are within the range of $10^6$, and since $2^{20} = 1048576$, the number of $1$s in binary representation can be at most $20$. The prime numbers within $20$ are $[2, 3, 5, 7, 11, 13, 17, 19]$.

1

2

3

4

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        primes = {2, 3, 5, 7, 11, 13, 17, 19}
        return sum(i.bit_count() in primes for i in range(left, right + 1))

Continue Practicing

#779 k th symbol in grammar #782 transform to chessboard #805 split array with same average