Problem 137

Abstract / Summary

Find the number that appears once in an array where every other number appears exactly three times.

Note

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

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
17 lines | 502 bytes | submitted August 15, 2023 | GitHub   15% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 68% (1+ million submissions).

Typical patterns to solve this problem:
  • Array
  • Bit Manipulation
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 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.

written by openai gpt

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.

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 | μ = 7.52 | σ = 0.74

Complexity Analysis

Time: linear
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
generated automatically

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++ 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++
51 links | 32 authors | 10 languages

Videos

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

Similar Problems

2 similar problems

Solved On The Same Day

30 solutions   August 15, 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