LeetCode 136: Single Number

Problem Restatement

We are given a non-empty integer array nums.

Every element appears exactly twice except for one element.

We need to return the element that appears only once.

The solution must run in linear time and use constant extra space. LeetCode states this explicitly in the problem requirements.

Examples

Example 1:

nums = [2, 2, 1]

The number 2 appears twice.

The number 1 appears once.

Output:

1

Example 2:

nums = [4, 1, 2, 1, 2]

The numbers 1 and 2 appear twice.

The number 4 appears once.

Output:

4

Example 3:

nums = [1]

There is only one number, so it is the answer.

Output:

1

Input and Output

Function shape:

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        ...

First Thought: Count Frequencies

A simple solution is to count how many times each number appears.

For example:

nums = [4, 1, 2, 1, 2]

The counts are:

Then we return the number with count 1.

This works, but it uses a hash map.

The space complexity is O(n), so it violates the constant-space requirement.

Key Insight

Use XOR.

XOR has three useful properties:

So if we XOR every number in the array, all duplicate pairs cancel out.

For example:

4 ^ 1 ^ 2 ^ 1 ^ 2

Reorder mentally:

(1 ^ 1) ^ (2 ^ 2) ^ 4

The duplicate pairs become zero:

0 ^ 0 ^ 4 = 4

So the remaining value is the single number.

Algorithm

Initialize:

answer = 0

Then scan every number:

answer ^= num

At the end, return answer.

Correctness

Every number except one appears exactly twice.

When a duplicate number is XORed with itself, it becomes 0.

Because XOR is associative and commutative, the order of operations does not affect the final result.

Therefore, all paired numbers cancel out.

The only number that does not have a matching pair remains in the final XOR result.

So the algorithm returns exactly the single number.

Complexity

Let n = len(nums).

Implementation

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        answer = 0

        for num in nums:
            answer ^= num

        return answer

Code Explanation

Start from zero:

answer = 0

This works because XOR with zero keeps the number unchanged.

Then process each number:

for num in nums:
    answer ^= num

Each duplicate pair cancels itself.

After the loop, only the single number remains:

return answer

Testing

def run_tests():
    s = Solution()

    assert s.singleNumber([2, 2, 1]) == 1
    assert s.singleNumber([4, 1, 2, 1, 2]) == 4
    assert s.singleNumber([1]) == 1
    assert s.singleNumber([-1, 2, 2]) == -1
    assert s.singleNumber([0, 1, 0]) == 1

    print("all tests passed")

run_tests()

Test meaning: