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.
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; }}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.