Prime Number of Set Bits in Binary Representation - Video Solutions

Problem Overview: Given two integers left and right, count how many numbers in this range have a prime number of set bits (1s) in their binary representation. For each integer, convert it conceptually to binary, count the 1s, and check whether that count is a prime number.

Approach 1: Bit Counting with Set Checking (Time: O(n * log W), Space: O(1))

Iterate through every number from left to right. For each number, count the number of set bits using a popcount operation (such as __builtin_popcount in C++ or bin(x).count('1') in Python). Once you have the count, check whether it belongs to a small predefined set of prime numbers like {2,3,5,7,11,13,17,19}. The key insight is that the maximum number of bits for the constraint range is small, so the possible set-bit counts are limited. This approach is simple, readable, and relies on basic bit manipulation and math concepts.

Approach 2: Optimized Prime Check with Bit Manipulation (Time: O(n), Space: O(1))

This approach removes the explicit prime lookup structure and encodes prime counts inside a bitmask. First compute the number of set bits for each number using a fast popcount operation. Then check primality using a precomputed mask such as 665772, where the binary representation stores which counts are prime. The check becomes (mask >> count) & 1. This turns the prime test into a constant-time bit operation. The idea leverages properties of small primes and keeps the entire solution in pure bitwise arithmetic. It is extremely compact and common in competitive programming solutions involving bit manipulation.

Recommended for interviews: The bit counting with prime set approach is what most interviewers expect first. It clearly shows you understand binary representation, set-bit counting, and basic prime logic. The bitmask optimization is a nice follow-up that demonstrates deeper familiarity with bit tricks and constant-time checks.