Skip to main content
Talentd

Prime Number of Set Bits in Binary Representation - Solution & Explanation

EasyMathBit Manipulation17 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

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

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).

In the C implementation, we define helper functions for checking prime status and counting set bits. We iterate from left to right, use the helper function to count the set bits, and check if it is prime.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * b) where n is the difference between right and left, and b is the number of bits in the binary representation of the number.
Space Complexity: O(1) since we're using a fixed amount of extra space.

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.

The C solution uses the GCC-specific built-in function __builtin_popcount for efficient bit counting, combined with bit-masking to check primality. The primes are stored as active bits in an integer representing a mask.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) with efficient bit manipulations.
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].

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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 in the binary representation of the number.
Space Complexity: O(1) since we're using a fixed amount of extra space.

Optimized Prime Check with Bit Manipulation

Time Complexity: O(n) with efficient bit manipulations.
Space Complexity: O(1).

Math + Bit Manipulation—

Detailed Complexity Analysis

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

Video Solution

Prime Number of Set Bits in Binary Representation | Simple Approach | Leetcode 762 | MIK • codestorywithMIK • 3,760 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Prime Number of Set Bits in Binary Representation with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of 1 Bits