Python 0137.py
class Solution:
def singleNumber(self, nums: List[int]) -> int:
# count bits, result will consists of bits which aren't multiples of 3
bits = [0] * 32
for i in nums:
for j in range(32):
if i & (1 << j):
bits[j] += 1
result = 0
for j in range(32):
result += (bits[j] % 3) << j
# two-complement
if result >= 2**31:
result -= 2**32
return result
Difficulty
and has an acceptance rate of about 68% (1+ million submissions).
Typical patterns to solve this problem:
- Array
- Bit Manipulation
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 implementation solves the classic “single number” problem where every element in the input list appears exactly three times except for one unique element that appears once. The algorithm works by aggregating the contribution of each bit position across all numbers, extracting the bits that are not multiples of three, and finally reconstructing the integer value. It also correctly interprets the result as a signed 32-bit integer using two’s-complement conversion.
Bit Counting Phase
The first major step creates a fixed-size container for the 32 bit positions and iterates through the list, incrementing the count for each set bit.
bits = [0] * 32
for i in nums:
for j in range(32):
if i & (1 << j):
bits[j] += 1
By using a plain Python list of length 32, the code avoids dynamic resizing and keeps the memory footprint constant regardless of the input size. The inner loop examines each bit with a simple mask and a bitwise AND, which is a very fast primitive operation.
Result Construction Phase
After the counts are collected, the algorithm reduces each count modulo three and assembles the final integer by shifting the remainder back into its original position.
result = 0
for j in range(32):
result += (bits[j] % 3) << j
The modulo operation isolates the bits belonging to the unique number because any bit contributed by the triply-occurring elements will be a multiple of three and thus reduced to zero. The shift-and-add pattern builds the integer in a single pass over the 32 positions.
Two’s-Complement Adjustment
Python integers have arbitrary precision, so the raw bit pattern must be interpreted as a signed 32-bit value. The code checks whether the most significant bit (the sign bit) is set and, if so, converts the unsigned representation to its negative two’s-complement equivalent.
if result >= 2**31:
result -= 2**32
return result
This conditional subtraction correctly maps values in the range [2**31, 2**32-1] to [-2**31, -1], ensuring that negative results are returned in the expected signed form.
Edge Cases Handled
When the input list contains only the unique element, the bit counting loop still processes a single number, and the modulo step yields the original bits unchanged, so the correct value is returned.
If the unique number is zero, every bit count remains a multiple of three, the modulo operation yields zero for each position, and the final result stays zero.
Negative numbers are represented in two’s-complement form within the 32-bit space. During counting, the sign bit is treated like any other bit, and the final adjustment step translates the unsigned pattern back to a signed integer, preserving the correct negative value.
The algorithm also works when the list includes the maximum positive 32-bit integer (2**31-1) or the most negative value (-2**31). The fixed 32-bit container and the two’s-complement correction guarantee that these boundary values are processed without overflow or loss of information.
Performance Optimizations Observed
The use of a constant-size array (bits = [0] * 32) eliminates the need for hash maps or dynamic data structures, which would introduce additional overhead.
Bitwise operations (&, <<) are employed throughout, leveraging the processor’s native support for these instructions and avoiding slower arithmetic alternatives.
The algorithm performs exactly two passes over the 32 bit positions, regardless of the length of nums. This predictable access pattern benefits from CPU caching, as the small bits array fits comfortably in cache lines.
Finally, the conditional two’s-complement conversion is executed only once after the entire result has been assembled, preventing repeated sign handling during the main loops. This separation keeps the hot loops tight and focused on counting and assembling bits.
ELI5 - Simplified Explanation
Imagine that all the numbers hidden in the list are made of tiny glowing lightbulbs. Each number has thirty-two spots where a lightbulb could be either on or off. The goal is to find the special number that is different from all others.
First, a big tray is prepared with thirty-two slots to keep track of how many lightbulbs are turned on for every single spot across all the numbers. Every number from the list is checked one by one. For each number, thirty-two tiny checks look to see if a lightbulb is glowing. If a bulb is on, a point is added to the corresponding slot in the tray.
After looking at every number, the tray tells a story about which bulbs were turned on most often. Since most numbers appear in groups of three, many of the lightbulb spots will have a total count that is a multiple of three. When those bits are divided by three and the remainder is taken, the leftovers show exactly which lightbulbs belong to the special single number.
To put the pieces back together, the code looks at each slot in the tray and shifts the results back into their proper places to build the final number. Because computers sometimes use a special way of counting to represent negative numbers, there is one last check to see if the result is very large. If it is too big, it is adjusted to make sure it matches the original hidden number.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
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++ | Python | Java | ||||||||
| leetcode.ca | C++ | Python | Rust | JS | Java | C | TS | Go | Swift | ||
| LeetcodeHelp | C++ | Python | Java | ||||||||
| MemoryLimitExceeded | C++ | Python | |||||||||
| Progiez | C++ | Python | Java | ||||||||
| github | aylei | Rust | |||||||||
| begeekmyfriend | C | ||||||||||
| BigEggStudy | C# | ||||||||||
| black-shadows | C++ | ||||||||||
| charles-wangkai | Java | ||||||||||
| chenyanzhe | C++ | ||||||||||
| everthis | JS | ||||||||||
| gaosq0604 | Python | ||||||||||
| halfrost | Go | ||||||||||
| haoel | Python | ||||||||||
| JoshCrozier | JS | ||||||||||
| keineahnung2345 | C++ | ||||||||||
| linouk23 | C++ | ||||||||||
| lkwq007 | Python | ||||||||||
| luangong | C++ | TS | |||||||||
| MacJim | C++ | ||||||||||
| qiyuangong | Python | ||||||||||
| ruoru | Rust | ||||||||||
| shreymehul | C# | ||||||||||
| suxrobGM | C# | ||||||||||
| varunu28 | Java | ||||||||||
| vli02 | C | ||||||||||
| wisdompeak | C++ | ||||||||||
| XiaotaoGuo | C++ | ||||||||||
| YuriSpiridonov | Python | ||||||||||
| zfang399 | C++ | ||||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||||
| WalkCCC | C++, Python, Java | ||||||||||
| leetcode.ca | C, C++, Go, Java, JavaScript, Python, Rust, Swift, TypeScript | ||||||||||
| LeetcodeHelp | C++, Java, Python | ||||||||||
| MemoryLimitExceeded | Python, C++ | ||||||||||
| Progiez | C++, Java, Python | ||||||||||
| aylei | Rust | ||||||||||
| begeekmyfriend | C | ||||||||||
| BigEggStudy | C# | ||||||||||
| black-shadows | C++, C++ | ||||||||||
| charles-wangkai | Java | ||||||||||
| chenyanzhe | C++ | ||||||||||
| everthis | JavaScript | ||||||||||
| gaosq0604 | Python | ||||||||||
| halfrost | Go | ||||||||||
| haoel | Python | ||||||||||
| JoshCrozier | JavaScript | ||||||||||
| keineahnung2345 | C++ | ||||||||||
| linouk23 | C++ | ||||||||||
| lkwq007 | Python | ||||||||||
| luangong | C++, TypeScript | ||||||||||
| MacJim | C++ | ||||||||||
| qiyuangong | Python | ||||||||||
| ruoru | Rust | ||||||||||
| shreymehul | C# | ||||||||||
| suxrobGM | C# | ||||||||||
| varunu28 | Java | ||||||||||
| vli02 | C | ||||||||||
| wisdompeak | C++ | ||||||||||
| XiaotaoGuo | C++ | ||||||||||
| YuriSpiridonov | Python | ||||||||||
| zfang399 | C++ |
Videos
Similar Problems
- problem 136: Single Number
- problem 260: Single Number III
Solved On The Same Day
- problem 112: Path Sum
- problem 409: Longest Palindrome
- problem 645: Set Mismatch
- problem 717: 1-bit and 2-bit Characters
- problem 2535: Difference Between Element Sum and Digit Sum of an Array
- problem 16: 3Sum Closest
- problem 24: Swap Nodes in Pairs
- problem 113: Path Sum II
- problem 114: Flatten Binary Tree to Linked List
- problem 116: Populating Next Right Pointers in Each Node
- problem 129: Sum Root to Leaf Numbers
- problem 131: Palindrome Partitioning
- problem 162: Find Peak Element
- problem 165: Compare Version Numbers
- problem 172: Factorial Trailing Zeroes
- problem 201: Bitwise AND of Numbers Range
- problem 204: Count Primes
- problem 402: Remove K Digits
- problem 430: Flatten a Multilevel Doubly Linked List
- problem 451: Sort Characters By Frequency
- problem 539: Minimum Time Difference
- problem 583: Delete Operation for Two Strings
- problem 633: Sum of Square Numbers
- problem 648: Replace Words
- problem 650: 2 Keys Keyboard
- problem 670: Maximum Swap
- problem 786: K-th Smallest Prime Fraction
- problem 2507: Smallest Value After Replacing With Sum of Prime Factors
- problem 2523: Closest Prime Numbers in Range
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