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.

Here’s a quick recap of the steps:

  1. Convert each number in the range to its binary representation.
  2. Count the number of set bits (1s) in this representation.
  3. Determine if this count is a prime number.
  4. Return the total count of such numbers.

Clarifying Questions

  1. Input Constraints:
    • What is the range of left and right? Can they be negative, or are they always positive?
      • Both left and right will be between 1 and 10^6, inclusive.
  2. Prime Definition:
    • Should we consider 1 as a prime number?
      • No, in standard mathematical definitions, 1 is not considered a prime number.
  3. Output:
    • The function should return a single integer representing the count of numbers with a prime number of set bits.

Strategy

  1. Precompute Primes:
    • Since counts of set bits for numbers within the given range will not be very high, we can precompute which numbers from 0 to 20 (highest count of set bits within the range 1 to 10^6) are prime.
  2. Count Set Bits:
    • For each number in the range ([left, right]), convert the number to its binary representation and count the number of 1s.
  3. Checking Prime Set Bits:
    • Use the precomputed primes to check if the number of set bits is prime.
  4. Code the Solution:
    • Iterate through the range and apply the above checks.

Code

Here’s the implementation in Java:

import java.util.HashSet;
import java.util.Set;

public class Solution {
    private static final Set<Integer> primes = new HashSet<>();

    static {
        primes.add(2);
        primes.add(3);
        primes.add(5);
        primes.add(7);
        primes.add(11);
        primes.add(13);
        primes.add(17);
        primes.add(19);
    }

    private int countSetBits(int n) {
        int count = 0;
        while (n > 0) {
            count += (n & 1);
            n >>= 1;
        }
        return count;
    }

    public int countPrimeSetBits(int left, int right) {
        int count = 0;
        for (int i = left; i <= right; i++) {
            if (primes.contains(countSetBits(i))) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        // Example test case
        System.out.println(sol.countPrimeSetBits(6, 10)); // Output: 4
    }
}

Time Complexity

  1. Precomputation:
    • Creating the set of prime numbers up to 20 is O(1) since the size of the set is constant and small.
  2. Main Loop over Range [left, right]:
    • Looping from left to right is O(n), where n is (right - left + 1).
  3. Counting Set Bits for Each Number:
    • Counting set bits for each number can be done in O(log(m)), where m is the maximum possible value within the range, which is 10^6. Converting and counting bits involves iterating over the bits, resulting in O(log(m)).

Combining these, the overall time complexity is O(n * log(m)), which simplifies to O(n * log(n)) for this specific problem with constraints, where n is (right - left + 1) and m is 10^6. This is efficient enough for the given problem constraints.

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