Prime Number of Set Bits in Binary Representation Python/Java solution

In Python, iterate through the range and use bin(x).count('1') to count set bits, then check if the count is in a prime set. In Java, Integer.bitCount(x) provides a fast popcount operation. Both implementations run in O(n) time with constant extra space.

How to solve Prime Number of Set Bits in Binary Representation in O(n)?

Iterate through every integer in the range [left, right], compute the number of set bits using a built-in popcount or bit trick, and verify whether that count is prime. A common optimization is using a bitmask constant that encodes all prime counts and checking with (mask >> count) & 1. This makes the prime validation constant time.

What is the best approach for Prime Number of Set Bits in Binary Representation?

The most practical approach is iterating from left to right, counting set bits for each number, and checking if that count is prime using a small predefined set. Since the maximum possible bit count is small, this check is constant time. The overall complexity is O(n) for the range traversal with O(1) extra space.

Is Prime Number of Set Bits in Binary Representation asked at Google/Amazon/Meta?

This problem reflects common interview themes such as bit manipulation, binary representation, and small mathematical checks. Similar questions appear in coding interviews at companies like Amazon, Google, and Microsoft when testing familiarity with bit operations and efficient counting techniques.

What data structure is used in Prime Number of Set Bits in Binary Representation?

The solution mainly relies on bit manipulation rather than complex data structures. Some implementations use a small hash set or array containing prime numbers for quick membership checks. More optimized versions replace the set with a bitmask integer for constant-time validation.

What is the time complexity of Prime Number of Set Bits in Binary Representation?

The time complexity is O(n) where n = right - left + 1. Each number requires a popcount operation to count set bits and a constant-time prime check. Space complexity remains O(1) because only a few integers or a small prime set are stored.

Description Hints 1 Solution Video 8:00

762. Prime Number of Set Bits in Binary Representation

Q: Is Prime Number of Set Bits in Binary Representation easy or hard?

The problem is classified as Easy on LeetCode with a high acceptance rate around 78%. It mainly tests understanding of binary representation, counting set bits, and simple prime checking rather than complex algorithms.

Easy78.7% acceptance2 companies

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.

Recall that the number of set bits an integer has is the number of 1's present when written in binary.

For example, 21 written in binary is 10101, which has 3 set bits.

Example 1:

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

Example 2:

Input: left = 10, right = 15
Output: 5
Explanation:
10 -> 1010 (2 set bits, 2 is prime)
11 -> 1011 (3 set bits, 3 is prime)
12 -> 1100 (2 set bits, 2 is prime)
13 -> 1101 (3 set bits, 3 is prime)
14 -> 1110 (3 set bits, 3 is prime)
15 -> 1111 (4 set bits, 4 is not prime)
5 numbers have a prime number of set bits.

Constraints:

1 <= left <= right <= 10⁶
0 <= right - left <= 10⁴

Asked at 2 companies

Amazon

Google

Topics

Bit Manipulation Math

Hints open one at a time

Hint 1

Write a helper function to count the number of set bits in a number, then check whether the number of set bits is 2, 3, 5, 7, 11, 13, 17 or 19.

8:00

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution