🏰Beginner-Friendly Guide 'Prime Number of Set Bits in Binary Representation' - Problem 762 (C++, Python, JavaScript)

Source: Dev.to

Problem Summary

You’re given:
Two integers, left and right, which define an inclusive range of numbers.

Your goal:
Count how many numbers within that range have a “set bit” count (the number of 1s in their binary representation) that is a prime number.

Intuition: How it Works

To solve this problem we perform two tasks for every number in the range:

1. Count the set bits.
   Example: 6 → binary 110 → set bits = 2.

2. Check if that count is prime.
   A prime number is a natural number greater than 1 with no positive divisors other than 1 and itself.
   Since right ≤ 10⁶, the maximum possible number of set bits is about 20, making the primality test trivial.

Walkthrough: Understanding the Example

For left = 6 and right = 10:

Total Count: 4

The Solutions

C++ Implementation

class Solution {
public:
    // Helper function to check if a number is prime
    bool isPrime(int x) {
        if (x  int:
        def is_prime(x: int) -> bool:
            if x  {
        if (x < 2) return false;
        for (let i = 2; i * i <= x; i++) {
            if (x % i === 0) return false;
        }
        return true;
    };

    let ans = 0;
    for (let i = left; i <= right; i++) {
        // Convert to binary string and count '1's
        let setBits = i.toString(2).split('1').length - 1;
        if (isPrime(setBits)) {
            ans++;
        }
    }
    return ans;
};

Python Implementation

def is_prime(x: int) -> bool:
    if x  {

JavaScript Implementation

let ans = 0;
for (let i = left; i <= right; i++) {
    // Convert to binary string and count '1's
    let setBits = i.toString(2).split('1').length - 1;
    if (isPrime(setBits)) {
        ans++;
    }
}
return ans;

Key Takeaways

• Bit Manipulation: Understanding binary representation is fundamental for writing efficient code.
• Helper Functions: Isolating logic (e.g., isPrime) improves readability and maintainability.
• Language Utilities: Each language offers convenient ways to work with bits—C++’s __builtin_popcount, Python’s bin, and JavaScript’s toString(2).

Final Thoughts

This problem introduces essential bitwise operations. While it appears as a simple math puzzle, the ability to count and manipulate bits is crucial in areas such as cryptography and compressed data structures. Mastering these basics prepares you for more complex “bitmasking” challenges often encountered in senior‑level engineering interviews.