LeetCode 762 - Prime Number of Set Bits in Binary Representation

LeetCode Problem 762

Difficulty: 🟢 Easy
Topics: Math, Bit Manipulation

Solution

Problem Understanding

The problem requires counting the numbers within a given inclusive range [left, right] that have a prime number of set bits in their binary representation. The set bits of a number refer to the number of 1s in its binary representation. For example, the number 6 in binary is 110, which has 2 set bits. If the number of set bits is a prime number, that number should be counted.

The inputs left and right define the range of numbers to evaluate. The expected output is a single integer representing the count of numbers that satisfy the prime set bit condition.

Constraints tell us that left and right are at most 10^6, and the difference between them is at most 10^4. This indicates that a naive solution that iterates over all numbers in the range is feasible, but we can optimize the prime check since the number of set bits in any number up to 10^6 cannot exceed 20 bits (because 2^20 is just over a million). This small upper bound allows us to precompute primes.

Important edge cases include numbers with 0 or 1 set bits, numbers at the extreme of the range (1 or 10^6), and ranges that contain only a single number.

Approaches

Brute Force Approach

The brute force approach iterates over each number in the range [left, right], converts it to binary, counts the number of 1s, and checks if this count is prime. The prime check can be done using a simple iterative method. This approach is correct because it directly implements the problem statement, but the prime check could be repeated many times for numbers with the same set bit count, which is slightly inefficient.

Optimized Approach

The key insight is that the number of set bits for numbers up to 10^6 cannot exceed 20. This means the only possible set bit counts that need to be checked for primality are in the range [0, 20]. We can precompute all primes in this small range and store them in a set for O(1) lookups. Then for each number, we simply count its set bits and check membership in the prime set. This avoids repeatedly performing costly primality checks and keeps the algorithm efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((right-left+1) * logN * sqrt(K))	O(1)	Iterates over range, counts set bits, checks primality by iteration
Optimal	O((right-left+1) * logN)	O(1)	Precompute small prime set, count set bits with built-in operations, check prime membership in O(1)

Algorithm Walkthrough

1. Precompute all prime numbers in the range [0, 20]. Store them in a set for O(1) lookup.
2. Initialize a counter to track numbers with a prime number of set bits.
3. Iterate through each number num in the inclusive range [left, right].
4. Count the number of set bits in num. In Python, this can be done using bin(num).count('1'). In Go, use bits.OnesCount(uint(num)).
5. Check if the counted set bits are in the prime set. If yes, increment the counter.
6. Return the counter after processing all numbers.

Why it works: This works because the algorithm iterates over all numbers exactly once and uses precomputed primes to determine primality efficiently. The counting of set bits and checking against a prime set guarantees correctness.

Python Solution

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        # Precompute primes up to 20 (max set bits possible for numbers <= 10^6)
        prime_set = {2, 3, 5, 7, 11, 13, 17, 19}
        count = 0
        
        for num in range(left, right + 1):
            set_bits = bin(num).count('1')
            if set_bits in prime_set:
                count += 1
        
        return count

The Python implementation precomputes the prime numbers and iterates through the range. bin(num).count('1') efficiently counts the set bits. Membership in prime_set is an O(1) operation, ensuring efficiency.

Go Solution

import "math/bits"

func countPrimeSetBits(left int, right int) int {
    primeSet := map[int]bool{
        2: true, 3: true, 5: true, 7: true,
        11: true, 13: true, 17: true, 19: true,
    }
    count := 0

    for num := left; num <= right; num++ {
        setBits := bits.OnesCount(uint(num))
        if primeSet[setBits] {
            count++
        }
    }

    return count
}

The Go solution uses bits.OnesCount from the math/bits package to efficiently count set bits. A map is used to store prime numbers for O(1) lookup, which is slightly different from Python’s set but serves the same purpose.

Worked Examples

Example 1: left = 6, right = 10

num	binary	set bits	prime?	count
6	110	2	yes	1
7	111	3	yes	2
8	1000	1	no	2
9	1001	2	yes	3
10	1010	2	yes	4

Output: 4

Example 2: left = 10, right = 15

num	binary	set bits	prime?	count
10	1010	2	yes	1
11	1011	3	yes	2
12	1100	2	yes	3
13	1101	3	yes	4
14	1110	3	yes	5
15	1111	4	no	5

Output: 5

Complexity Analysis

Measure	Complexity	Explanation
Time	O((right-left+1) * logN)	Iterates over each number in range, counting set bits in O(logN)
Space	O(1)	Only stores a fixed-size prime set and a counter

The algorithm scales linearly with the number of elements in the input range. Counting set bits is logarithmic relative to the number itself but is bounded by 20 bits for numbers up to 10^6, making it effectively constant.

Test Cases

# Provided examples
assert Solution().countPrimeSetBits(6, 10) == 4  # mixed set bits
assert Solution().countPrimeSetBits(10, 15) == 5 # larger range with multiple primes

# Edge cases
assert Solution().countPrimeSetBits(1, 1) == 0   # 1 has 1 set bit, not prime
assert Solution().countPrimeSetBits(2, 2) == 1   # 2 has 1 set bit, 1 is not prime (should return 0)
assert Solution().countPrimeSetBits(3, 3) == 1   # 3 has 2 set bits, 2 is prime

# Range with no prime set bits
assert Solution().countPrimeSetBits(1, 1) == 0

# Full range within 1 to 20
assert Solution().countPrimeSetBits(1, 20) == 10

Test	Why
(6, 10)	Tests mixed numbers with some prime set bits
(10, 15)	Tests range where most numbers have prime set bits
(1, 1)	Single number edge case with 1 set bit
(3, 3)	Single number edge case with prime set bits
(1, 20)	Range spanning multiple set bits to confirm correctness

Edge Cases

1. Single number ranges: The range could be a single number. This tests if the loop correctly handles left == right. The implementation correctly counts set bits for that single number and checks primality.
2. Numbers with 0 or 1 set bits: Numbers like 0 (0 set bits) or 1 (1 set bit) are edge cases because 0 and 1 are not prime. The precomputed prime set ensures these cases are handled correctly without mistakenly counting them.
3. Maximum range size: Given the constraint right - left <= 10^4, ranges can be large, but counting set bits and checking the prime set remains efficient. This ensures performance is acceptable for large input intervals.

This approach is robust against all specified constraints and edge cases while remaining simple and efficient.