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
Difficulty
and has an acceptance rate of about 79% (300k+ submissions).
Typical patterns to solve this problem:
- Bit Manipulation
- Math
AI Disclaimer
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.
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.
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.
Code Quality
Complexity Analysis
Other Solutions
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++ |
Videos
Similar Problems
- problem 191: Number of 1 Bits
Solved On The Same Day
- problem 661: Image Smoother
- problem 693: Binary Number with Alternating Bits
- problem 319: Bulb Switcher
- problem 2336: Smallest Number in Infinite Set
- problem 679: 24 Game
Extra
- 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