Problem 762

Abstract / Summary

Count how many numbers in a range have a prime number of 1s in their binary form.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0762.py

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        result = 0

        primes = ( 2,3,5,7,11,13,17,19,23,29 )
        for i in range(left, right+1):
            if i.bit_count() in primes:
                result += 1

        return result
10 lines | 286 bytes | submitted September 10, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 79% (300k+ submissions).

Typical patterns to solve this problem:
  • Bit Manipulation
  • Math
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided Solution class implements a method countPrimeSetBits that receives two integers, left and right, defining an inclusive range. For every integer in this range the method counts how many have a number of set bits (bits equal to 1) that is a prime number. The final count is returned as an integer.

Key Steps

The method begins by initializing a counter named result to zero. This variable accumulates the number of integers whose set-bit count is prime.

result = 0

A tuple named primes stores the prime numbers that can possibly appear as the count of set bits for any 32-bit integer. The largest possible number of set bits for a non-negative integer fitting in 32 bits is 32, and the tuple includes all prime values up to that bound.

primes = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29)

The core of the algorithm is a for loop that iterates over every integer i from left through right, inclusive. For each i the built-in method bit_count() is invoked, which returns the number of 1-bits in the binary representation of i. The result of i.bit_count() is then checked for membership in the primes tuple. If the count is prime, result is incremented.

for i in range(left, right + 1):
    if i.bit_count() in primes:
        result += 1

After the loop finishes, the accumulated result is returned to the caller.

return result

Edge Cases Handled

The implementation gracefully handles the situation where left and right are equal, effectively reducing the loop to a single iteration and still correctly evaluating that single number. When the range includes the value zero, 0.bit_count() yields zero, which is not present in the primes tuple, so zero is correctly excluded from the count. The tuple of primes includes all relevant prime values up to 29, covering the maximum possible set-bit count for any integer within typical problem constraints; therefore, numbers with a set-bit count of 31 (which would be prime) are never encountered because the input domain does not exceed 10⁶, keeping the tuple sufficient for all valid inputs.

Performance Optimizations

The code leverages Python’s native int.bit_count() method, which is implemented in C and runs in constant time relative to the size of the integer’s binary representation. This avoids the overhead of manually iterating over bits or converting the number to a string. Storing the prime numbers in a tuple provides an immutable, hashable container that enables fast membership testing; the in operation on a tuple of small, fixed size executes in linear time over at most ten elements, which is negligible compared to the loop over the input range. By predefining the prime set rather than recomputing primality for each bit count, the algorithm eliminates repeated expensive checks, resulting in a tight inner loop that performs only two primitive operations per iteration: a bit count and a membership test. The overall structure-simple iteration with constant-time work per element-ensures that the method scales efficiently with the size of the input interval.

written by openai gpt

ELI5 - Simplified Explanation

Think of this code like a game where you go through a line of numbers. The game starts by picking a range, which is like a starting number and an ending number. You look at every single number between those two points one by one. For each number, you count how many ones are hiding inside its secret computer code. Computers write numbers using only zeros and ones. Once the total count of those ones is figured out, you check if that count is on a special list of lucky prime numbers. If the count matches one of the lucky numbers on the list, you give yourself a point. You keep doing this for every number in the range until you reach the very end. The final score keeps track of how many times you found a lucky count.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 8 | μ = 8.30 | σ = 0.90

Complexity Analysis

not analyzed yet

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Java
leetcode.ca C++ C# Rust Python Java Go TS
LeetcodeHelp C++ Python Java
Progiez C++ Python Java
github BigEggStudy C#
black-shadows C++
charles-wangkai Java
everthis JS
fartem Ruby
halfrost Go
JoshCrozier JS
keineahnung2345 C++
lkwq007 Python
lzl124631x C++
ruoru Rust
suxrobGM C#
vli02 C
withaarzoo C++
zfang399 C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Java
leetcode.ca C++, C#, Go, Java, Python, Rust, TypeScript
LeetcodeHelp C++, Java, Python
Progiez C++, Java, Python
BigEggStudy C#
black-shadows C++, C++
charles-wangkai Java
everthis JavaScript
fartem Ruby
halfrost Go
JoshCrozier JavaScript
keineahnung2345 C++
lkwq007 Python
lzl124631x C++
ruoru Rust
suxrobGM C#
vli02 C
withaarzoo C++
zfang399 C++
34 links | 20 authors | 10 languages

Videos

9 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

2 easy 2 medium 1 hard
6 solutions   September 10, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality