LeetCode 136 - Single Number

Difficulty: 🟢 Easy
Topics: Array, Bit Manipulation

Solution

Problem Understanding

The problem gives an integer array nums where every value appears exactly twice except for one value that appears only once. The task is to find and return that unique value.

The important part of the problem is not just finding the unique number, but doing so under strict constraints. The solution must run in linear time, O(n), and use only constant extra space, O(1).

The input array can contain positive numbers, negative numbers, and zero. The array length can be as large as 3 * 10^4, which means inefficient approaches can become too slow. Since every duplicated number appears exactly twice, there is a strong symmetry in the data that we can exploit.

The expected output is a single integer, the one value that does not have a duplicate partner.

Several edge cases are important to recognize immediately:

The array may contain only one element, in which case that element is the answer.
The unique number may appear at the beginning, middle, or end of the array.
The array may contain negative numbers.
A naive nested loop approach would work logically, but would violate the required time complexity.
A hash map based solution would satisfy linear time, but would violate the constant space requirement.

The problem guarantees that exactly one number appears once and all others appear exactly twice, so we never need to handle invalid input configurations.

Approaches

Brute Force Approach

A straightforward approach is to check every number and count how many times it appears in the array.

For each element, we iterate through the entire array and count its frequency. If the frequency is one, we return that number.

This approach is correct because it explicitly verifies the occurrence count of every value. However, it is inefficient because for each of the n elements, we may scan the entire array again.

This leads to a time complexity of O(n^2), which becomes unnecessarily slow as the input grows larger.

Another common beginner solution uses a hash map to count frequencies. That improves the runtime to O(n) but requires O(n) extra space, which violates the problem requirement.

Optimal Approach, Bit Manipulation with XOR

The key observation is the behavior of the XOR operation.

XOR has several useful properties:

a ^ a = 0
a ^ 0 = a
XOR is commutative and associative

This means that when we XOR all numbers together:

Every duplicated number cancels itself out
Only the unique number remains

For example:

2 ^ 2 ^ 1
= 0 ^ 1
= 1

Because we only maintain a single running XOR value, the solution uses constant extra space. Since we traverse the array once, the runtime is linear.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Counts occurrences using nested loops
Optimal	O(n)	O(1)	Uses XOR cancellation property

Algorithm Walkthrough

Initialize a variable called result to 0.

We use 0 because XOR with zero leaves a number unchanged. This makes it the ideal starting value for accumulation. 2. Traverse through every number in the array.

We process each element exactly once, which ensures linear runtime. 3. XOR the current number with result.

result = result ^ num

If a number appears twice, the two occurrences cancel each other out because a ^ a = 0. 4. Continue until all numbers are processed.

After all duplicate pairs eliminate themselves, only the unique number remains stored in result. 5. Return result.

This final value is the single number that appeared only once.

Why it works

The correctness comes from the cancellation property of XOR. Since every duplicated value appears exactly twice, each pair produces zero when XORed together. XOR is associative and commutative, so the order does not matter. After all duplicate pairs cancel out, only the unique number remains.

Python Solution

from typing import List

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

        for num in nums:
            result ^= num

        return result

The implementation begins by initializing result to 0. This variable stores the running XOR of all numbers processed so far.

The loop iterates through every number in nums. During each iteration, the current value is XORed with result.

If the number has appeared before, the two occurrences cancel each other out. If the number is unique, it remains in the accumulated XOR result.

At the end of the traversal, every duplicated number has been eliminated, leaving only the single non duplicated number. The method then returns this value.

Go Solution

func singleNumber(nums []int) int {
    result := 0

    for _, num := range nums {
        result ^= num
    }

    return result
}

The Go implementation follows the same logic as the Python version.

The range loop iterates through the slice and retrieves each number. The XOR assignment operator ^= updates the running result efficiently.

No special handling for empty input is required because the problem guarantees the array is non empty. Integer overflow is not a concern because XOR operates at the bit level without arithmetic growth.

Worked Examples

Example 1

Input:

nums = [2, 2, 1]

Step	Current Number	Result Before	Result After
Start	-	0	0
1	2	0	2
2	2	2	0
3	1	0	1

Final answer:

The two 2s cancel each other out, leaving only 1.

Example 2

Input:

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

Step	Current Number	Result Before	Result After
Start	-	0	0
1	4	0	4
2	1	4	5
3	2	5	7
4	1	7	6
5	2	6	4

Final answer:

The duplicated 1s and 2s cancel out, leaving 4.

Example 3

Input:

nums = [1]

Step	Current Number	Result Before	Result After
Start	-	0	0
1	1	0	1

Final answer:

Since there is only one element, it is immediately returned.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	The array is traversed exactly once
Space	O(1)	Only one extra variable is used

The runtime is linear because each element is processed a single time. The space usage remains constant because the algorithm stores only the running XOR result, regardless of input size.

Test Cases

sol = Solution()

assert sol.singleNumber([2, 2, 1]) == 1  # basic example
assert sol.singleNumber([4, 1, 2, 1, 2]) == 4  # unique number at beginning
assert sol.singleNumber([1]) == 1  # single element array

assert sol.singleNumber([0, 1, 1]) == 0  # unique zero
assert sol.singleNumber([-1, -1, -2]) == -2  # negative numbers
assert sol.singleNumber([5, 3, 5]) == 3  # unique number in middle
assert sol.singleNumber([7, 8, 8]) == 7  # unique number at beginning
assert sol.singleNumber([9, 9, 10]) == 10  # unique number at end

assert sol.singleNumber([100]) == 100  # smallest valid size
assert sol.singleNumber([-30000, 1, 1]) == -30000  # lower constraint boundary
assert sol.singleNumber([30000, -2, -2]) == 30000  # upper constraint boundary

assert sol.singleNumber([2, 3, 2, 4, 4]) == 3  # multiple duplicate pairs
assert sol.singleNumber([6, 1, 6, 2, 2]) == 1  # unique surrounded by duplicates

Test	Why
`[2, 2, 1]`	Basic example from problem statement
`[4, 1, 2, 1, 2]`	Multiple duplicate pairs
`[1]`	Minimum possible array size
`[0, 1, 1]`	Ensures zero works correctly with XOR
`[-1, -1, -2]`	Verifies handling of negative numbers
`[5, 3, 5]`	Unique element in the middle
`[7, 8, 8]`	Unique element at beginning
`[9, 9, 10]`	Unique element at end
`[100]`	Single element boundary case
`[-30000, 1, 1]`	Lower constraint boundary
`[30000, -2, -2]`	Upper constraint boundary
`[2, 3, 2, 4, 4]`	Several cancellation operations
`[6, 1, 6, 2, 2]`	Interleaved duplicates

Edge Cases

Single Element Array

An array containing only one element is the smallest valid input. A buggy implementation might incorrectly assume at least one duplicated pair exists. The XOR solution handles this naturally because 0 ^ x = x, so the lone value is returned directly.

Negative Numbers

Some implementations incorrectly assume XOR only works for positive integers. Bitwise XOR works correctly for signed integers as well. The algorithm treats negative numbers exactly the same way as positive ones, so duplicated negative values still cancel out properly.

Unique Value at Any Position

The unique number may appear at the beginning, middle, or end of the array. Order does not matter because XOR is commutative and associative. The implementation processes values sequentially, but the final result remains correct regardless of arrangement.