# Prime Number of Set Bits in Binary Representation **Difficulty:** EASY [External](https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation) Canonical: https://scaleengineer.com/dsa/problems/prime-number-of-set-bits-in-binary-representation **Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation) --- ## 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 <= 106` * `0 <= right - left <= 104` # Approaches ## Brute Force with Naive Primality Test 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. **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. **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. ### Explanation 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. ```java 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; } } ``` ### Algorithm - Initialize a counter `ans` to 0. - Iterate through each integer `i` from `left` to `right`. - For each `i`, create a helper function `countSetBits(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`) until `i` is 0. - For each resulting `bitCount`, create another helper function `isPrime(bitCount)` to check if it's a prime number. This function can iterate from 2 up to the square root of `bitCount` to check for divisors. - If `bitCount` is prime, increment `ans`. - After the loop finishes, return `ans`. ## Iteration with Pre-calculated Primes 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. **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. **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. ### Explanation 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. ```java import java.util.Arrays; import java.util.HashSet; import java.util.Set; class Solution { public int countPrimeSetBits(int left, int right) { Set 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; } } ``` ### Algorithm - Create a `HashSet` and populate it with all prime numbers up to 20 (2, 3, 5, 7, 11, 13, 17, 19). - Initialize a counter `ans` to 0. - Iterate through each integer `i` from `left` to `right`. - For each `i`, calculate the number of set bits, `bitCount`, using a simple loop (`while(n > 0)`). - Check if `bitCount` is present in the `HashSet`. - If it is, increment `ans`. - Return `ans`. ## Optimized Bit Counting with Pre-calculated Primes 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. **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. **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`. ### Explanation 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. ```java 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. ### Algorithm - Create a data structure for `O(1)` lookup of primes up to 20. A `HashSet`, a boolean array, or a single integer bitmask can be used. - Initialize a counter `ans` to 0. - Iterate through each integer `i` from `left` to `right`. - For each `i`, use a built-in function like `Integer.bitCount(i)` to find the number of set bits, `bitCount`. - Check if `bitCount` is a prime using the pre-computed data structure. - If it is, increment `ans`. - Return `ans`. # Solutions ### Java ```java class Solution { private static Set 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; } } ``` ### CPP ```cpp class Solution { public: int countPrimeSetBits(int left, int right) { unordered_set 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; } }; ``` ### Python ```python 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)) ```