762. Prime Number of Set Bits in Binary Representation LeetCode Solution
In this guide, you will get 762. Prime Number of Set Bits in Binary Representation LeetCode Solution with the best time and space complexity. The solution to Prime Number of Set Bits in Binary Representation problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Prime Number of Set Bits in Binary Representation
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.
1 <= left <= right <= 106
0 <= right – left <= 104
Complexity Analysis
Time Complexity: O(R – L + 1)
Space Complexity: O(1)
762. Prime Number of Set Bits in Binary Representation LeetCode Solution in C++
class Solution {
public:
int countPrimeSetBits(int left, int right) {
// {2, 3, 5, 7, 11, 13, 17, 19}-th bits are 1s.
// 0b10100010100010101100 = 665772
constexpr int magic = 665772;
int ans = 0;
for (unsigned num = left; num <= right; ++num)
if (magic >> popcount(num) & 1)
++ans;
return ans;
}
}; /* code provided by PROGIEZ */
762. Prime Number of Set Bits in Binary Representation LeetCode Solution in Java
class Solution {
public int countPrimeSetBits(int left, int right) {
// {2, 3, 5, 7, 11, 13, 17, 19}-th bits are 1s.
// 0b10100010100010101100 = 665772
final int magic = 665772;
int ans = 0;
for (int num = left; num <= right; ++num)
if ((magic >> Integer.bitCount(num) & 1) == 1)
++ans;
return ans;
}
} // code provided by PROGIEZ
762. Prime Number of Set Bits in Binary Representation LeetCode Solution in Python
