LeetCode 137 - Single Number II

LeetCode Problem 137

Difficulty: 🟡 Medium
Topics: Array, Bit Manipulation

Solution

Problem Understanding

This problem asks us to find a unique number in an array where every other number appears exactly three times. In simpler terms, if you imagine counting all the numbers in the array, every number except one will show up three times, and our task is to identify the number that only appears once.

The input is a list of integers nums, with a size constraint of up to 3 * 10^4, which is relatively large. The numbers themselves can be negative, zero, or positive, up to the 32-bit signed integer range. The output is a single integer, the number that does not repeat three times.

Edge cases to keep in mind include arrays with the smallest size of 1 (where the only number is the answer), arrays with negative numbers, and arrays where the unique number is zero. The problem guarantees that there is exactly one unique number, so we do not need to handle multiple single numbers or empty arrays.

The key challenge is that the solution must run in linear time and use constant extra space, which rules out typical approaches using hash maps or sorting.

Approaches

The brute-force approach is to use a hash map or dictionary to count the occurrences of each number. Once all counts are known, we can iterate through the dictionary to find the number that occurs once. This approach is simple and correct, but it uses O(n) extra space, which violates the problem's constant space constraint.

The optimal approach leverages bit manipulation. Since numbers are integers with a fixed number of bits (32 bits in this case), we can examine each bit position across all numbers. For each bit position, if we sum all the bits in that position across the array and take modulo 3, the sum will be zero for bits belonging to numbers appearing three times. The remaining sum will correspond to the bits of the unique number. Using this insight, we can reconstruct the single number without extra memory beyond a few integer variables.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Use a hash map to count occurrences, simple but violates constant space constraint
Optimal	O(n)	O(1)	Use bitwise operations to track bits counts modulo 3, reconstruct the single number efficiently

Algorithm Walkthrough

1. Initialize two integer variables, ones and twos, to zero. These variables will track bits that have appeared once and twice respectively.
2. Iterate over each number num in the array.
3. Update twos with bits that have appeared twice. This is done using twos |= ones & num.
4. Update ones with bits that have appeared once. Use ones ^= num.
5. Compute a mask for bits that have appeared three times: common_mask = ~(ones & twos).
6. Clear the bits in ones and twos that have appeared three times: ones &= common_mask and twos &= common_mask.
7. After processing all numbers, ones will contain the bits of the unique number. Return ones.

Why it works:

The algorithm maintains a bitwise count of appearances modulo 3 for each bit position. Whenever a bit has appeared three times, it is cleared from both ones and twos, effectively resetting the count for that bit. At the end, only the bits corresponding to the unique number remain in ones.

Python Solution

from typing import List

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ones, twos = 0, 0
        for num in nums:
            twos |= ones & num
            ones ^= num
            common_mask = ~(ones & twos)
            ones &= common_mask
            twos &= common_mask
        return ones

In this implementation, ones keeps track of bits seen once, twos keeps track of bits seen twice, and common_mask clears bits that have appeared three times. By the end, ones contains the unique number.

Go Solution

func singleNumber(nums []int) int {
    ones, twos := 0, 0
    for _, num := range nums {
        twos |= ones & num
        ones ^= num
        commonMask := ^(ones & twos)
        ones &= commonMask
        twos &= commonMask
    }
    return ones
}

The Go implementation mirrors the Python solution. We use integers ones and twos to track bit counts, and commonMask to reset bits that have appeared three times. Go's bitwise operations work identically to Python for 32-bit integers.

Worked Examples

Example 1: nums = [2,2,3,2]

Iteration	num	ones	twos	common_mask
1	2	2	0	-1
2	2	0	2	-3
3	3	1	2	-2
4	2	3	0	-1

Final ones = 3 → output 3.

Example 2: nums = [0,1,0,1,0,1,99]

Iteration	num	ones	twos	common_mask
1	0	0	0	-1
2	1	1	0	-1
3	0	1	0	-1
4	1	0	1	-2
5	0	0	0	-1
6	1	0	0	-1
7	99	99	0	-1

Final ones = 99 → output 99.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each number is processed once, and all bitwise operations are constant time.
Space	O(1)	Only a fixed number of integer variables are used, independent of input size.

The solution meets the requirement of linear runtime with constant extra space.

Test Cases

# provided examples
assert Solution().singleNumber([2,2,3,2]) == 3  # basic test
assert Solution().singleNumber([0,1,0,1,0,1,99]) == 99  # unique at the end

# edge cases
assert Solution().singleNumber([7]) == 7  # only one element
assert Solution().singleNumber([0,0,0,-1]) == -1  # negative unique
assert Solution().singleNumber([1,1,1,0]) == 0  # unique is zero
assert Solution().singleNumber([-2,-2,-2,-5]) == -5  # negative numbers
assert Solution().singleNumber([10**6,10**6,10**6,123456]) == 123456  # large numbers

Test	Why
[2,2,3,2]	Basic functionality with small positive numbers
[0,1,0,1,0,1,99]	Unique number at the end, mixed values
[7]	Single-element array
[0,0,0,-1]	Negative unique number
[1,1,1,0]	Unique is zero
[-2,-2,-2,-5]	All numbers negative
[106,106,10**6,123456]	Large numbers to check bit handling

Edge Cases

Single-element array: If the array has only one element, it is trivially the unique number. Our implementation handles this naturally because the loop runs once, and ones ends up as that element.

Negative numbers: Bit manipulation works correctly with negative numbers in Python and Go because the operations apply to the two's complement binary representation. This ensures ones reconstructs negative numbers correctly.

Unique number is zero: Zero has no set bits, so it might seem tricky, but the algorithm handles it correctly because ones starts at zero and will remain zero if all numbers appear three times except zero. This ensures zero is returned accurately.