Prime Number of Set Bits in Binary Representation
EasyPrompt
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,
21written in binary is10101, which has3set 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 <= 1060 <= right - left <= 104
Approaches
3 approaches with complexity analysis and trade-offs.
This approach iterates through every number in the given range [left, right]. For each number, it first counts the number of set bits in its binary representation and then checks if this count is a prime number using a trial division method.
Algorithm
- Initialize a counter
ansto 0. - Iterate through each integer
ifromlefttoright. - For each
i, create a helper functioncountSetBits(i)to calculate the number of set bits. This can be done by repeatedly checking the last bit (i & 1) and right-shifting (i >>= 1) untiliis 0. - For each resulting
bitCount, create another helper functionisPrime(bitCount)to check if it's a prime number. This function can iterate from 2 up to the square root ofbitCountto check for divisors. - If
bitCountis prime, incrementans. - After the loop finishes, return
ans.
Walkthrough
The main logic involves a loop from left to right. Inside the loop, for each number i, we need two helper functions: countSetBits(n) and isPrime(n). The countSetBits(n) function takes an integer n and returns the number of '1's in its binary form. It can be implemented by repeatedly checking the last bit (n & 1) and right-shifting the number (n >>= 1) until n becomes 0. The isPrime(n) function checks if a number n is prime. A simple way is to check for divisibility from 2 up to the square root of n. We also handle base cases like n <= 1. The main function calls these helpers for each number in the range and increments a counter if the bit count is prime.
class Solution { public int countPrimeSetBits(int left, int right) { int count = 0; for (int i = left; i <= right; i++) { int setBits = countSetBits(i); if (isPrime(setBits)) { count++; } } return count; } private int countSetBits(int n) { int bits = 0; while (n > 0) { bits += n & 1; n >>= 1; } return bits; } private boolean isPrime(int n) { if (n <= 1) { return false; } for (int i = 2; i * i <= n; i++) { if (n % i == 0) { return false; } } return true; }}Complexity
Time
O((right - left) * log(right)). The main loop runs `right - left + 1` times. Inside the loop, counting set bits for a number `n` takes `O(log n)` time. The primality test for the bit count `p` takes `O(sqrt(p))`. Since the maximum value of `right` is `10^6`, the maximum bit count is less than 20. Thus, the primality test runs in constant time. The dominant part inside the loop is counting the bits.
Space
O(1). No extra space is used besides a few variables for counting and iteration.
Trade-offs
Pros
Easy to understand and implement from first principles.
Doesn't require any pre-computation or knowledge of specific constraints.
Cons
The primality test is performed repeatedly, which is inefficient, although not a major bottleneck here due to the small input to
isPrime.The bit counting loop is slightly less efficient than built-in methods or other algorithms like Brian Kernighan's.
This approach improves upon the brute-force method by optimizing the primality check. Given the constraint right <= 10^6, the maximum number of bits in any number is 20 (since 2^19 < 10^6 < 2^20). Therefore, the number of set bits will be at most 20. We can pre-calculate or hardcode the prime numbers up to 20 and store them in a data structure that allows for fast lookups, like a hash set.
Algorithm
- Create a
HashSetand populate it with all prime numbers up to 20 (2, 3, 5, 7, 11, 13, 17, 19). - Initialize a counter
ansto 0. - Iterate through each integer
ifromlefttoright. - For each
i, calculate the number of set bits,bitCount, using a simple loop (while(n > 0)). - Check if
bitCountis present in theHashSet. - If it is, increment
ans. - Return
ans.
Walkthrough
First, we identify all prime numbers less than or equal to 20, which are 2, 3, 5, 7, 11, 13, 17, and 19. We store these primes in a HashSet for O(1) average time complexity lookups. Then, we iterate from left to right. For each number, we count its set bits using the same simple loop as in the previous approach. Instead of calling an isPrime function, we check if the bit count exists in our pre-computed set of primes. If it does, we increment our result counter.
import java.util.Arrays;import java.util.HashSet;import java.util.Set; class Solution { public int countPrimeSetBits(int left, int right) { Set<Integer> primes = new HashSet<>(Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19)); int count = 0; for (int i = left; i <= right; i++) { int setBits = countSetBits(i); if (primes.contains(setBits)) { count++; } } return count; } private int countSetBits(int n) { int bits = 0; while (n > 0) { bits += n & 1; n >>= 1; } return bits; }}Complexity
Time
O((right - left) * log(right)). The loop runs `right - left + 1` times. Counting set bits takes `O(log(right))` time. The lookup in the hash set is `O(1)` on average.
Space
O(1). The space used by the hash set is constant because the number of primes up to 20 is fixed and does not depend on the input size.
Trade-offs
Pros
Much faster primality check (
O(1)) compared to the naive approach.Still relatively simple to implement.
Cons
The manual bit counting method is not as fast as built-in functions.
This is the most efficient approach. It combines the pre-calculated primes from the previous approach with a highly optimized method for counting set bits. Most programming languages provide a built-in function to count the number of set bits (e.g., Integer.bitCount() in Java, __builtin_popcount() in C++). These functions are often implemented using special CPU instructions and are extremely fast.
Algorithm
- Create a data structure for
O(1)lookup of primes up to 20. AHashSet, a boolean array, or a single integer bitmask can be used. - Initialize a counter
ansto 0. - Iterate through each integer
ifromlefttoright. - For each
i, use a built-in function likeInteger.bitCount(i)to find the number of set bits,bitCount. - Check if
bitCountis a prime using the pre-computed data structure. - If it is, increment
ans. - Return
ans.
Walkthrough
The core idea is the same: iterate through the range, count set bits, and check if the count is a prime. The optimization comes from using Integer.bitCount(i) to get the number of set bits for each number i. This is significantly faster than a manual loop. The primality check is done using a pre-computed set of primes. A boolean array or even a single integer bitmask can be used for this, which might be slightly faster than a hash set due to better cache locality and no hashing overhead.
class Solution { public int countPrimeSetBits(int left, int right) { // Primes up to 20 (max bits for 10^6) are 2, 3, 5, 7, 11, 13, 17, 19. // We can use a bitmask for an O(1) check. // The mask is created by setting the bits at prime indices: (1<<2)|(1<<3)|(1<<5)|... int primeMask = 665772; // In binary: 10100010100010101100 int count = 0; for (int i = left; i <= right; i++) { int setBits = Integer.bitCount(i); // Check if the bit corresponding to setBits is set in our primeMask if ((primeMask & (1 << setBits)) != 0) { count++; } } return count; }}The code snippet uses a clever bitmask trick for the primality check. A number p is considered "prime" for our purposes if the p-th bit is set in the primeMask. For example, to check if 3 is prime, we check if (1 << 3) is set in the mask. This avoids using a HashSet and can be slightly faster.
Complexity
Time
O(right - left). The loop runs `right - left + 1` times. Inside the loop, both `Integer.bitCount()` and the primality check using the bitmask are effectively `O(1)` operations for 32-bit integers.
Space
O(1). The space for the prime lookup data structure (the integer mask) is constant.
Trade-offs
Pros
Optimal time complexity.
Very concise and efficient code.
Cons
Relies on built-in functions which might obscure the underlying logic for beginners.
The bitmask trick for primality check is clever but might be less readable than a
HashSet.
Solutions
Solution
class Solution {private static Set<Integer> primes = Set.of(2, 3, 5, 7, 11, 13, 17, 19);public int countPrimeSetBits(int left, int right) { int ans = 0; for (int i = left; i <= right; ++i) { if (primes.contains(Integer.bitCount(i))) { ++ans; } } return ans; }}class Solution {public: int countPrimeSetBits(int left, int right) { unordered_set<int> primes{2, 3, 5, 7, 11, 13, 17, 19}; int ans = 0; for (int i = left; i <= right; ++i) ans += primes.count(__builtin_popcount(i)); return ans; }};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))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.