DSAPrep
EasyBit Manipulation

Single Number

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1

Input: nums = [2,2,1]
Output: 1

Example 2

Input: nums = [4,1,2,1,2]
Output: 4

Example 3

Input: nums = [1]
Output: 1

Constraints

  • 1 <= nums.length <= 3 * 10^4
  • -3 * 10^4 <= nums[i] <= 3 * 10^4
  • Each element in the array appears twice except for one element which appears only once.
View original on LeetCode ↗

The space constraint rules out a hash set of seen values (that would be O(n) space). The trick is a property of XOR: x ^ x = 0 and x ^ 0 = x, and XOR is commutative and associative. So if every value except one appears exactly twice, XOR-ing the whole array together cancels every paired value down to zero, leaving only the value that appeared once.

Hash Set

Time O(n)Space O(n)

Walk the array, adding each new value to a set and removing it if it is already there. Whatever remains in the set at the end is the answer.

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        seen = set()
        for num in nums:
            if num in seen:
                seen.remove(num)
            else:
                seen.add(num)
        return seen.pop()

This works, but it uses O(n) space for the set, which violates the “constant extra space” requirement even though it is linear time.

XOR Accumulator

OptimalTime O(n)Space O(1)

XOR every number in the array into a running accumulator, starting at 0. Each value that appears twice XORs with itself and vanishes (x ^ x = 0); the leftover value XORs with 0 and survives (x ^ 0 = x). Since XOR does not care about order, it does not matter where the duplicates and the single value fall in the array.

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        result = 0
        for num in nums:
            result ^= num
        return result

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

i
4
0
1
1
2
2
1
3
2
4
result = 4
1 / 5
resultcurrent

result = 0 ^ 4 = 4.

Correctness: XOR is commutative and associative, so the order of operations does not matter — the final accumulator equals the XOR of all distinct values that appear an odd number of times, which here is exactly the single number.

Complexity: one pass over the array with O(1) work per element → O(n) time. Only a single integer accumulator is kept → O(1) space, satisfying the constraint the hash set approach could not.