algoadvance

Leetcode 762. Prime Number of Set Bits in Binary Representation

Problem Statement

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.

Definition: A set bit is a bit that has a value of 1.

Example:

Input: left = 6, right = 10
Output: 4
Explanation:
6  -> 110 (2 set bits, which is prime)
7  -> 111 (3 set bits, which is prime)
8  -> 1000 (1 set bit, not prime)
9  -> 1001 (2 set bits, which is prime)
10 -> 1010 (2 set bits, which is prime)

Note:

• left <= right <= 10^6
• 1 ≤ left, right ≤ 10^6

Clarifying Questions

1. What is the range of the possible values of left and right?
   • Both left and right can range from 1 to 10^6.
2. What is the maximum number of bits we need to consider in the binary representation of a number in the given range?
   • Numbers up to 10^6 can be represented in binary with at most 20 bits.

Strategy

1. Count Set Bits Function:
   • We need a helper function to count the number of set bits (1s) in the binary representation of a number.
2. Prime Checking Function:
   • Create a helper function to determine if a given number is prime. Given that the number of bits will be <= 20, we just need to check for primality up to this limit.
3. Iterate and Count:
   • Iterate through the numbers from left to right, count the set bits, and check if this count is a prime number. If yes, increase the result count.

Code

#include <iostream>
#include <vector>
#include <bitset>

// Function to check if a number is prime
bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

// Function to count the number of set bits in binary representation
int countSetBits(int n) {
    return std::bitset<21>(n).count(); // 21 to handle up to 20 bits
}

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

int main() {
    int left = 6;
    int right = 10;
    
    std::cout << countPrimeSetBits(left, right) << std::endl; // Output: 4
    
    return 0;
}

Time Complexity

• The countSetBits function uses bitset which operates in O(1) for a fixed number representation (21 bits in this case).
• The isPrime function, in worst case, performs operations proportional to the square root of n (up to 20 in this scenario).
• Overall, the loop from left to right is O(n), where n is the length of the range.

Therefore, the overall time complexity is O(n * sqrt(m)), where n is the range [left, right] and m is the maximum number of set bits (in this case, up to 20, a constant). This simplifies the overall complexity to O(n) given the constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?