⚠️ This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#136) before relying on it.

Single Number

An interactive visualization of the XOR bit manipulation technique. Watch how XOR properties elegantly find the single non-duplicate number by canceling out pairs.

Bit Manipulation LeetCode 136 ↗ Easy

The Problem

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.

Interactive Visualization

Array (comma-separated)

Preset

Speed:

Array Visualization

XOR Accumulator

0b00000000

Code

fun singleNumber(nums: IntArray): Int {    var result = 0    for (num in nums)        result = result xor num    return result}

def singleNumber(nums):    result = 0    for num in nums:        result ^= num    return result

Status

Press Step or Play to begin.

How It Works

Key Insight

The XOR operation has special properties that make it perfect for this problem: a ⊕ a = 0 (any number XOR'd with itself equals zero) and a ⊕ 0 = a (any number XOR'd with zero equals itself). Since XOR is also commutative and associative, all the duplicate pairs cancel out to zero, leaving only the single unique number.

The Algorithm

Initialize: result = 0 (XOR identity element)
Iterate: For each number in the array, XOR it with the accumulator: result ^= num
Pairs cancel: When the same number appears twice, num ^ num = 0, effectively removing both from the result
Unique remains: The single number that appears only once will remain after all pairs have canceled out
Return: The final result is the single non-duplicate number

Complexity

Time O(n)

Space O(1)

We iterate through the array once, performing a constant-time XOR operation on each element. We only use a single variable to track the result, so space complexity is constant regardless of input size.