LeetCode 762: Prime Number of Set Bits in Binary Representation Solution

Master LeetCode problem 762 (Prime Number of Set Bits in Binary Representation), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

762. Prime Number of Set Bits in Binary Representation

Easy

Math Bit Manipulation

Problem Explanation

Explanation

To solve this problem, we iterate over the range [left, right], count the number of set bits in each number's binary representation, and then check if this count is a prime number. We can implement a helper function isPrime to determine if a number is prime. Finally, we return the count of numbers with a prime number of set bits.

Algorithm:

Define a helper function isPrime to check if a number is prime.
Initialize a variable count to 0 to keep track of the numbers with a prime number of set bits.
Iterate over the range [left, right]:
- Count the number of set bits in the binary representation of the current number.
- Check if this count is a prime number using the isPrime function.
- If it is prime, increment the count.
Return the final count.

Time Complexity:

The time complexity of this solution is O((right-left) * log(log(right)) + (right-left) * sqrt(right)).

Space Complexity:

The space complexity of this solution is O(1).

Solution Code

class Solution {
    public int countPrimeSetBits(int left, int right) {
        int count = 0;
        for (int i = left; i <= right; i++) {
            int numSetBits = Integer.bitCount(i);
            if (isPrime(numSetBits)) {
                count++;
            }
        }
        return count;
    }

    private boolean isPrime(int n) {
        if (n <= 1) return false;
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 762 (Prime Number of Set Bits in Binary Representation)?

This page provides optimized solutions for LeetCode problem 762 (Prime Number of Set Bits in Binary Representation) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 762 (Prime Number of Set Bits in Binary Representation)?

The time complexity for LeetCode 762 (Prime Number of Set Bits in Binary Representation) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 762 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 762 in Java, C++, or Python.

Back to LeetCode Solutions