Prime Number of Set Bits in Binary Representation

Difficulty: Easy | Acceptance: 78.80% | Paid: No Topics: Math, Bit Manipulation

Given two integers left and right, find 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 in its binary representation.

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

• Examples
• Constraints
• Approach 1: Brute Force with Prime Check
• Approach 2: Precompute Primes
• Approach 3: Brian Kernighan’s Algorithm
• Approach 4: Lookup Table

Examples

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.

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^6

Approach 1: Brute Force with Prime Check

Intuition Iterate through each number in the range, count its set bits, and check if that count is prime using a simple primality test.

Steps

• Initialize count to 0
• For each number from left to right:
  • Count set bits using built-in function or manual counting
  • Check if the count is prime
  • If prime, increment count
• Return count

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

Complexity

• Time: O((right - left + 1) × log(right) × √(log(right)))
• Space: O(1)
• Notes: Simple but not optimal due to repeated prime checks

Approach 2: Precompute Primes

Intuition Since the maximum value is 10⁶, the maximum number of set bits is 20 (2²⁰ = 1,048,576). We can precompute all primes up to 20 and use a set for O(1) lookup.

Steps

• Create a set of primes up to 20: 19
• For each number from left to right:
  • Count set bits
  • Check if count is in the prime set
  • If yes, increment count
• Return count

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        primes = {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 primes:
                count += 1
        return count

Complexity

• Time: O((right - left + 1) × log(right))
• Space: O(1)
• Notes: Much faster than brute force due to O(1) prime lookup

Approach 3: Brian Kernighan’s Algorithm

Intuition Use Brian Kernighan’s algorithm to efficiently count set bits by repeatedly clearing the lowest set bit, combined with precomputed primes.

Steps

• Create a set of primes up to 20
• For each number from left to right:
  • Count set bits using Brian Kernighan’s algorithm (n & (n-1) clears lowest set bit)
  • Check if count is in prime set
  • If yes, increment count
• Return count

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        primes = {2, 3, 5, 7, 11, 13, 17, 19}
        
        def count_set_bits(n):
            count = 0
            while n:
                n &= n - 1
                count += 1
            return count
        
        result = 0
        for num in range(left, right + 1):
            if count_set_bits(num) in primes:
                result += 1
        return result

Complexity

• Time: O((right - left + 1) × k) where k is the number of set bits
• Space: O(1)
• Notes: Brian Kernighan’s algorithm is efficient for sparse bit patterns

Approach 4: Lookup Table

Intuition Precompute the number of set bits for all numbers up to 10⁶ using dynamic programming, then simply lookup and check if prime.

Steps

• Create a lookup table where table[i] = number of set bits in i
• Use the relation: table[i] = table[i >> 1] + (i & 1)
• Create a set of primes up to 20
• For each number from left to right:
  • Get set bits from lookup table
  • Check if in prime set
  • If yes, increment count
• Return count

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        primes = {2, 3, 5, 7, 11, 13, 17, 19}
        
        max_n = 10**6
        set_bits = [0] * (max_n + 1)
        for i in range(1, max_n + 1):
            set_bits[i] = set_bits[i >> 1] + (i & 1)
        
        count = 0
        for num in range(left, right + 1):
            if set_bits[num] in primes:
                count += 1
        return count

Complexity

• Time: O(maxN) for precomputation + O(right - left + 1) for query
• Space: O(maxN)
• Notes: Best for multiple queries, but uses extra space