762. Prime Number of Set Bits Solution

The problem

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⁴

Approach overview

Problem Overview: Given two integers left and right, count how many numbers in this range have a prime number of set bits (1s) in their binary representation. For each integer, convert it conceptually to binary, count the 1s, and check whether that count is a prime number.

Approach 1: Bit Counting with Set Checking (Time: O(n * log W), Space: O(1))

Iterate through every number from left to right. For each number, count the number of set bits using a popcount operation (such as __builtin_popcount in C++ or bin(x).count('1') in Python). Once you have the count, check whether it belongs to a small predefined set of prime numbers like {2,3,5,7,11,13,17,19}. The key insight is that the maximum number of bits for the constraint range is small, so the possible set-bit counts are limited. This approach is simple, readable, and relies on basic bit manipulation and math concepts.

Approach 2: Optimized Prime Check with Bit Manipulation (Time: O(n), Space: O(1))

This approach removes the explicit prime lookup structure and encodes prime counts inside a bitmask. First compute the number of set bits for each number using a fast popcount operation. Then check primality using a precomputed mask such as 665772, where the binary representation stores which counts are prime. The check becomes (mask >> count) & 1. This turns the prime test into a constant-time bit operation. The idea leverages properties of small primes and keeps the entire solution in pure bitwise arithmetic. It is extremely compact and common in competitive programming solutions involving bit manipulation.

Recommended for interviews: The bit counting with prime set approach is what most interviewers expect first. It clearly shows you understand binary representation, set-bit counting, and basic prime logic. The bitmask optimization is a nice follow-up that demonstrates deeper familiarity with bit tricks and constant-time checks.

Approach 1: Bit Counting with Set Checking

This approach involves iterating over each number in the specified range, counting the number of set bits (1s in the binary representation), and checking if the count is a prime number. We use a predefined set of prime numbers up to 19, since the number of set bits can at most be around 20 (using log base 2 of the maximum value 10^6).

Python

def is_prime(num):
    if num <= 1:
        return False
    primes = {2, 3, 5, 7, 11, 13, 17, 19}
    return num in primes


def count_prime_set_bits(left, right):
    prime_set_count = 0
    for num in range(left, right + 1):
        set_bits = bin(num).count('1')
        if is_prime(set_bits):
            prime_set_count += 1
    return prime_set_count

if __name__ == "__main__":
    left, right = 6, 10
    print(count_prime_set_bits(left, right))

Java

import java.util.HashSet;
import java.util.Set;

public class PrimeSetBits {
    private static Set<Integer> primes = new HashSet<>() {{
        add(2); add(3); add(5); add(7); add(11); add(13); add(17); add(19);
    }};

    public static boolean isPrime(int num) {
        return primes.contains(num);
    }

    public static int countPrimeSetBits(int left, int right) {
        int count = 0;
        for (int i = left; i <= right; i++) {
            if (isPrime(Integer.bitCount(i))) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int left = 6, right = 10;
        System.out.println(countPrimeSetBits(left, right));
    }
}

C++

#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

bool is_prime(int num) {
    if (num <= 1) return false;
    vector<int> primes = {2, 3, 5, 7, 11, 13, 17, 19};
    for (int p : primes) {
        if (num == p) return true;
    }
    return false;
}

int countPrimeSetBits(int left, int right) {
    int prime_set_count = 0;
    for (int num = left; num <= right; num++) {
        int set_bits = __builtin_popcount(num);
        if (is_prime(set_bits)) prime_set_count++;
    }
    return prime_set_count;
}

int main() {
    int left = 6, right = 10;
    cout << countPrimeSetBits(left, right) << endl;
    return 0;
}

JavaScript

function isPrime(num) {
  const primes = new Set([2, 3, 5, 7, 11, 13, 17, 19]);
  return primes.has(num);
}

function countSetBits(n) {
  return n.toString(2).split('1').length - 1;
}

function countPrimeSetBits(left, right) {
  let count = 0;
  for (let i = left; i <= right; i++) {
    if (isPrime(countSetBits(i))) {
      count++;
    }
  }
  return count;
}

console.log(countPrimeSetBits(6, 10));

#include <stdio.h>
#include <stdbool.h>

bool is_prime(int num) {
    if (num <= 1) return false;
    if (num <= 3) return true;
    if (num % 2 == 0 || num % 3 == 0) return false;
    for (int i = 5; i * i <= num; i += 6) {
        if (num % i == 0 || num % (i + 2) == 0) return false;
    }
    return true;
}

int count_set_bits(int num) {
    int count = 0;
    while (num > 0) {
        count += num & 1;
        num >>= 1;
    }
    return count;
}

int countPrimeSetBits(int left, int right) {
    int count = 0;
    for (int num = left; num <= right; num++) {
        int set_bits = count_set_bits(num);
        if (is_prime(set_bits)) {
            count++;
        }
    }
    return count;
}

int main() {
    int left = 6, right = 10;
    printf("%d\n", countPrimeSetBits(left, right));
    return 0;
}

using System;
using System.Collections.Generic;

class PrimeSetBits {
    static HashSet<int> primeSet = new HashSet<int> { 2, 3, 5, 7, 11, 13, 17, 19 };

    static bool IsPrime(int number) {
        return primeSet.Contains(number);
    }

    static int CountPrimeSetBits(int left, int right) {
        int count = 0;
        for (int i = left; i <= right; i++) {
            int setBits = Convert.ToString(i, 2).Replace("0", "").Length;
            if (IsPrime(setBits)) {
                count++;
            }
        }
        return count;
    }

    static void Main(string[] args) {
        int left = 6, right = 10;
        Console.WriteLine(CountPrimeSetBits(left, right));
    }
}

The Python implementation uses a set for small prime numbers and the string method count to determine set bits efficiently for each number in the range.

Complexity

Time Complexity: O(n * b) where n is the difference between right and left, and b is the number of bits.
Space Complexity: O(1).

Try this approach in the editor

Approach 2: Optimized Prime Check with Bit Manipulation

This optimized approach employs direct bit manipulation for counting the set bits and uses a bit mask for prime number checking, representing the primality of counts using bits instead of hash sets or arrays.

Python

def count_prime_set_bits(left, right):
    prime_mask = 0b10100010100010101100
    count = 0
    for num in range(left, right + 1):
        set_bits = bin(num).count('1')
        if prime_mask & (1 << set_bits):
            count += 1
    return count

if __name__ == "__main__":
    print(count_prime_set_bits(6, 10))

Java

public class OptimizedPrimeSetBits {
    public static int countPrimeSetBits(int left, int right) {
        int count = 0;
        int primeMask = 0b00000000000010100010100010100000;
        for (int i = left; i <= right; i++) {
            int bits = Integer.bitCount(i);
            if ((primeMask & (1 << bits)) != 0) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(countPrimeSetBits(6, 10));
    }
}

C++

#include <iostream>
using namespace std;

int countPrimeSetBits(int left, int right) {
    int count = 0;
    int prime_mask = (1 << 2) | (1 << 3) | (1 << 5) | (1 << 7) | (1 << 11) | (1 << 13) | (1 << 17) | (1 << 19);
    for (int n = left; n <= right; n++) {
        int bits = __builtin_popcount(n);
        if (prime_mask & (1 << bits))
            count++;
    }
    return count;
}

int main() {
    int left = 6, right = 10;
    cout << countPrimeSetBits(left, right) << endl;
    return 0;
}

JavaScript

function countPrimeSetBits(left, right) {
  const primeMask = 0b10100010100010101100;
  let count = 0;

  for (let n = left; n <= right; n++) {
    const bits = n.toString(2).split('1').length - 1;
    if ((primeMask & (1 << bits)) !== 0) {
      count++;
    }
  }

  return count;
}

console.log(countPrimeSetBits(6, 10));

#include <stdio.h>

int countPrimeSetBits(int left, int right) {
    int count = 0;
    int prime_mask = (1 << 2) | (1 << 3) | (1 << 5) | (1 << 7) | (1 << 11) | (1 << 13) | (1 << 17) | (1 << 19);
    for (int n = left; n <= right; n++) {
        int bits = __builtin_popcount(n);
        if (prime_mask & (1 << bits))
            count++;
    }
    return count;
}

int main() {
    int left = 6, right = 10;
    printf("%d\n", countPrimeSetBits(left, right));
    return 0;
}

using System;

class OptimizedPrimeSetBits {
    static int CountPrimeSetBits(int left, int right) {
        int count = 0;
        int primeMask = 0b00000000000010100010100010100000;
        for (int i = left; i <= right; i++) {
            int bits = Convert.ToString(i, 2).Split('1').Length - 1;
            if ((primeMask & (1 << bits)) != 0) {
                count++;
            }
        }
        return count;
    }

    static void Main() {
        Console.WriteLine(CountPrimeSetBits(6, 10));
    }
}

Python's implementation stores the prime status of small numbers as bits in an integer, verifiable using bitwise AND, providing a compact solution.

Complexity

Time Complexity: O(n), efficient scanning using optimized bit processing.
Space Complexity: O(1).

Try this approach in the editor

Approach 3: Math + Bit Manipulation

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

We enumerate each number in the range [left,.. right], count the number of 1s in its binary representation, and then check if this count is a prime number. If it is, we increment the answer by one.

The time complexity is O(ntimes log m), where n = right - left + 1 and m is the maximum number in the range [left,.. right].

TypeScript

function countPrimeSetBits(left: number, right: number): number {
    const primes = new Set<number>([2, 3, 5, 7, 11, 13, 17, 19]);
    let ans = 0;

    for (let i = left; i <= right; i++) {
        const bits = bitCount(i);
        if (primes.has(bits)) {
            ans++;
        }
    }

    return ans;
}

function bitCount(i: number): number {
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

func countPrimeSetBits(left int, right int) (ans int) {
	primes := map[int]int{}
	for _, v := range []int{2, 3, 5, 7, 11, 13, 17, 19} {
		primes[v] = 1
	}
	for i := left; i <= right; i++ {
		ans += primes[bits.OnesCount(uint(i))]
	}
	return
}

Rust

impl Solution {
    pub fn count_prime_set_bits(left: i32, right: i32) -> i32 {
        let primes = [2, 3, 5, 7, 11, 13, 17, 19];
        let mut ans = 0;

        for i in left..=right {
            let bits = i.count_ones() as i32;
            if primes.contains(&bits) {
                ans += 1;
            }
        }

        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Bit Counting with Set Checking	Time Complexity: O(n * b) where n is the difference between right and left, and b is the number of bits. Space Complexity: O(1).
Optimized Prime Check with Bit Manipulation	Time Complexity: O(n), efficient scanning using optimized bit processing. Space Complexity: O(1).
Math + Bit Manipulation	–

Complexity analysis

Approach	Time	Space	When to Use
Bit Counting with Prime Set Checking	O(n * log W)	O(1)	Best for readability and interviews. Easy to implement with built-in popcount.
Optimized Prime Check with Bit Mask	O(n)	O(1)	When you want a compact constant-time prime check using bit manipulation.

Frequently asked questions

Is Prime Number of Set Bits in Binary Representation easy or hard?

The problem is classified as Easy on LeetCode with a high acceptance rate around 78%. It mainly tests understanding of binary representation, counting set bits, and simple prime checking rather than complex algorithms.

Prime Number of Set Bits in Binary Representation Python/Java solution

In Python, iterate through the range and use bin(x).count('1') to count set bits, then check if the count is in a prime set. In Java, Integer.bitCount(x) provides a fast popcount operation. Both implementations run in O(n) time with constant extra space.

How to solve Prime Number of Set Bits in Binary Representation in O(n)?

Iterate through every integer in the range [left, right], compute the number of set bits using a built-in popcount or bit trick, and verify whether that count is prime. A common optimization is using a bitmask constant that encodes all prime counts and checking with (mask >> count) & 1. This makes the prime validation constant time.

What is the best approach for Prime Number of Set Bits in Binary Representation?

The most practical approach is iterating from left to right, counting set bits for each number, and checking if that count is prime using a small predefined set. Since the maximum possible bit count is small, this check is constant time. The overall complexity is O(n) for the range traversal with O(1) extra space.

Is Prime Number of Set Bits in Binary Representation asked at Google/Amazon/Meta?

This problem reflects common interview themes such as bit manipulation, binary representation, and small mathematical checks. Similar questions appear in coding interviews at companies like Amazon, Google, and Microsoft when testing familiarity with bit operations and efficient counting techniques.

What data structure is used in Prime Number of Set Bits in Binary Representation?

The solution mainly relies on bit manipulation rather than complex data structures. Some implementations use a small hash set or array containing prime numbers for quick membership checks. More optimized versions replace the set with a bitmask integer for constant-time validation.

What is the time complexity of Prime Number of Set Bits in Binary Representation?

The time complexity is O(n) where n = right - left + 1. Each number requires a popcount operation to count set bits and a constant-time prime check. Space complexity remains O(1) because only a few integers or a small prime set are stored.

Prime Number of Set Bits in Binary Representation solution and explanation

The problem

Approach overview

Approach 1: Bit Counting with Set Checking

Approach 2: Optimized Prime Check with Bit Manipulation

Approach 3: Math + Bit Manipulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Prime Number of Set Bits in Binary Representation solution and explanation

The problem

Approach overview

Approach 1: Bit Counting with Set Checking

Approach 2: Optimized Prime Check with Bit Manipulation

Approach 3: Math + Bit Manipulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems