0Pricing
DSA Interview Prep · Lesson

Single Number and XOR Properties

Use XOR's self-inverse property to find the one element appearing once in a list where all others appear twice, then extend to single-number-II and III.

The Single Number Problem

The Single Number problem (LeetCode 136) asks: given an array where every element appears exactly twice except one, find the element that appears only once. The O(n) time and O(1) space constraint rules out hash maps (O(n) space) and sorting (O(n log n) time or O(n) space for the sort).

The elegant solution uses XOR. XOR every element together. Since identical elements cancel (a ^ a = 0) and XOR is commutative and associative, all paired elements vanish, leaving only the single element. This is one of the most satisfying O(n)/O(1) solutions in all of competitive programming.

def single_number(nums):
    result = 0
    for n in nums:
        result ^= n
    return result

# All pairs cancel, leaving the lone element
print(single_number([2, 2, 1]))              # 1
print(single_number([4, 1, 2, 1, 2]))        # 4
print(single_number([1]))                    # 1
print(single_number([7, 3, 5, 3, 7]))        # 5

# Even more concise with functools.reduce
from functools import reduce
from operator import xor
print(reduce(xor, [2, 2, 1]))  # 1

Why XOR Works: Three Key Properties

XOR's power comes from three algebraic properties working together:

  • Self-inverse: a ^ a = 0 — identical values cancel each other out
  • Identity: a ^ 0 = a — XOR with zero leaves values unchanged
  • Commutativity and Associativity: order does not matter, groupings do not matter

These three properties together mean that XOR over a multiset collapses all elements appearing an even number of times to 0, leaving only elements appearing an odd number of times. For Single Number I, exactly one element appears once (odd), so it is the XOR result.

# Demonstrating the three XOR properties
print('Self-inverse: a ^ a = 0')
for a in [5, 13, 255, 0]:
    print(f'  {a} ^ {a} = {a ^ a}')

print('Identity: a ^ 0 = a')
for a in [5, 13, 0, 1024]:
    print(f'  {a} ^ 0 = {a ^ 0}')

print('Commutativity and Associativity:')
a, b, c = 3, 5, 7
print(f'  a^b^c = {a^b^c}')
print(f'  c^a^b = {c^a^b}')  # same result
print(f'  (a^b)^c = {(a^b)^c}')
print(f'  a^(b^c) = {a^(b^c)}')  # same result

All lessons in this course

  1. Bitwise Operators: AND, OR, XOR, NOT, Shifts
  2. Single Number and XOR Properties
  3. Bit Masks: Set, Clear, Toggle, Check
  4. Counting Bits, Missing Number, and Reverse Bits
← Back to DSA Interview Prep