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.
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 <= 1060 <= right - left <= 104This 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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) with efficient bit manipulations.
Space Complexity: O(1).
| 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 in the binary representation of the number. |
| Optimized Prime Check with Bit Manipulation | Time Complexity: O(n) with efficient bit manipulations. |
Counting Bits - Dynamic Programming - Leetcode 338 - Python • NeetCode • 159,557 views views
Watch 9 more video solutions →Practice Prime Number of Set Bits in Binary Representation with our built-in code editor and test cases.
Practice on FleetCode