Leetcode 762: Prime Number of Set Bits in Binary Representation
grid47 Exploring patterns and algorithms
Aug 22, 2024
5 min read
Solution to LeetCode 762: Prime Number of Set Bits in Binary Representation 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. The number of set bits in a number is the count of 1’s when the number is represented in binary. A prime number is a number greater than 1 that is divisible only by 1 and itself.
Problem
Approach
Steps
Complexity
Input: The input consists of two integers, left and right.
Example: Input: left = 8, right = 15
Constraints:
• 1 <= left <= right <= 10^6
• 0 <= right - left <= 10^4
Output: Return an integer representing the count of numbers in the range [left, right] that have a prime number of set bits.
Example: Output: 4
Constraints:
• The answer is guaranteed to fit in a 32-bit integer.
Goal: The goal is to find how many numbers in the range [left, right] have a prime number of set bits.
Steps:
• For each number in the range [left, right], calculate the number of set bits.
• Check if the number of set bits is prime by using a pre-defined list of prime numbers.
• Count how many numbers have a prime number of set bits.
Goal: Constraints on the values of left and right.
Steps:
• 1 <= left <= right <= 10^6
• 0 <= right - left <= 10^4
Assumptions:
• The input integers left and right are within the given constraints.
• Input: Example 1: Input: left = 8, right = 15
• Explanation: In this example, the prime numbers of set bits are 2 and 3, and there are 4 numbers (9, 10, 11, 12) in the range [8, 15] that have a prime number of set bits.
Approach: We can solve this problem by iterating through each number in the given range and checking if the number of set bits is prime.
Observations:
• We can use a helper function to count the number of set bits in a number.
• We can precompute prime numbers up to 20 to efficiently check if a number of set bits is prime.
• The most efficient way to count the number of set bits is to use the __builtin_popcount function.
Steps:
• Define a list of prime numbers.
• For each number in the range [left, right], count the number of set bits.
• Check if the count of set bits is prime by using the list of prime numbers.
• Count and return how many numbers have a prime number of set bits.
Empty Inputs:
• If the range is very small or has a width of 0, there may be no numbers to check.
Large Inputs:
• The solution should efficiently handle the maximum possible input size (up to 10^6).
Special Values:
• The number 1 should be handled correctly, as it is not prime.
Constraints:
• Ensure the solution works for the maximum constraint where left and right can be as large as 10^6.
intcountPrimeSetBits(int left, int right) {
int prime[]={2, 3, 5, 7, 11, 13, 17, 19};
vector<bool> isPrime(21, 0);
for(intp: prime) isPrime[p]=1;
int sum=0;
for(int i=left; i<=right; i++){
int b=__builtin_popcount(i);
if (isPrime[b]) sum++;
}
return sum;
}
1 : Function Definition
intcountPrimeSetBits(int left, int right) {
This line defines the function 'countPrimeSetBits' which takes two integers 'left' and 'right' as input parameters and returns the count of numbers in the range [left, right] that have a prime number of set bits in their binary representation.
2 : Array Initialization
int prime[]={2, 3, 5, 7, 11, 13, 17, 19};
This initializes an array 'prime' containing the first few prime numbers. These will be used to check if the count of set bits in a number is prime.
3 : Vector Initialization
vector<bool> isPrime(21, 0);
This initializes a boolean vector 'isPrime' of size 21, all set to false. It will be used to track which numbers between 0 and 20 are prime.
4 : Prime Marking
for(intp: prime) isPrime[p]=1;
This loop iterates over the 'prime' array and marks the corresponding positions in the 'isPrime' vector as true for prime numbers.
5 : Variable Initialization
int sum=0;
This initializes a variable 'sum' to zero. This will keep track of how many numbers in the range have a prime number of set bits.
6 : Looping Over Range
for(int i=left; i<=right; i++){
This loop iterates through all numbers between 'left' and 'right' inclusive.
7 : Set Bit Counting
int b=__builtin_popcount(i);
This line calculates the number of set bits (1s) in the binary representation of 'i' using the '__builtin_popcount' function.
8 : Prime Check
if (isPrime[b]) sum++;
This checks if the count of set bits 'b' is a prime number by referring to the 'isPrime' vector. If it is, 'sum' is incremented.
9 : Return Statement
return sum;
This returns the final value of 'sum', which represents the count of numbers with a prime number of set bits in the range [left, right].
Best Case: O(1) when left == right.
Average Case: O(n) where n is the difference between right and left.
Worst Case: O(n) where n is the difference between right and left, with additional checks for set bits.
Description: The time complexity is mainly dependent on iterating over the range and checking the set bits for each number.
Best Case: O(1) for the space used.
Worst Case: O(1) for the space used by the prime list and the set bit calculation.
Description: The space complexity is minimal as we are only using a small list of primes and some basic variables.
