Module 25 · Bit Manipulation, Mathematics, and Designed Data Structures

241. Single Number with XOR

Foundation · Download this solution · All solutions and shared helpers

Problem

Given a nonempty integer list in which exactly one value occurs once and every other distinct value occurs exactly twice, return the single value. Negative integers are allowed. Use XOR accumulation and leave the input unchanged. The occurrence guarantee is a precondition, not something this algorithm verifies.

Examples

Example 1

single_number([4,1,2,1,2])
=> 4

Both repeated values cancel.

Example 2

single_number([-3,5,5])
=> -3

The identity works for negative integers too.

Example 3

single_number([0])
=> 0

The sole value can be zero.

Reveal the worked solution and reasoning

Why this mechanism works

XOR is associative and commutative, with x XOR x=0 and x XOR 0=x. Consequently each paired value cancels regardless of where its occurrences appear. The unmatched value survives. This is an algebraic summary of a prefix, rather than a frequency table.

State and boundaries

answer equals the XOR of all processed values. Its final value is determined by cancellation under the occurrence contract.

Protocol

Initialize answer to zero.
XOR each value into answer.
Return the accumulator.

Visualization

4 XOR 1 XOR 2 XOR 1 XOR 2
= 4 XOR (1 XOR 1) XOR (2 XOR 2)
= 4 XOR 0 XOR 0 = 4

Python implementation

def single_number(nums):
    answer = 0
    for value in nums:
        answer ^= value
    return answer

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

single_number([4,1,2,1,2])

L2 single_number: answer = 0
nums=[4, 1, 2, 1, 2]; answer=0

L3 single_number: for value in nums:
nums=[4, 1, 2, 1, 2]; answer=0; value=4

L4 single_number: answer ^= value
nums=[4, 1, 2, 1, 2]; answer=4; value=4

L3 single_number: for value in nums:
nums=[4, 1, 2, 1, 2]; answer=4; value=1

L4 single_number: answer ^= value
nums=[4, 1, 2, 1, 2]; answer=5; value=1

L3 single_number: for value in nums:
nums=[4, 1, 2, 1, 2]; answer=5; value=2

L4 single_number: answer ^= value
nums=[4, 1, 2, 1, 2]; answer=7; value=2

L3 single_number: for value in nums:
nums=[4, 1, 2, 1, 2]; answer=7; value=1

L4 single_number: answer ^= value
nums=[4, 1, 2, 1, 2]; answer=6; value=1

L3 single_number: for value in nums:
nums=[4, 1, 2, 1, 2]; answer=6; value=2

L4 single_number: answer ^= value
nums=[4, 1, 2, 1, 2]; answer=4; value=2

Result: 4. Both repeated values cancel.

single_number([-3,5,5])

L2 single_number: answer = 0
nums=[-3, 5, 5]; answer=0

L3 single_number: for value in nums:
nums=[-3, 5, 5]; answer=0; value=-3

L4 single_number: answer ^= value
nums=[-3, 5, 5]; answer=-3; value=-3

L3 single_number: for value in nums:
nums=[-3, 5, 5]; answer=-3; value=5

L4 single_number: answer ^= value
nums=[-3, 5, 5]; answer=-8; value=5

L4 single_number: answer ^= value
nums=[-3, 5, 5]; answer=-3; value=5

Result: -3. The identity works for negative integers too.

Why the solution is correct

The loop invariant follows directly from appending one more XOR term. At completion, associativity and commutativity allow equal terms to be paired and canceled, leaving precisely the sole unpaired value. Python's integer XOR identities also hold for negative integers.

Time and space

O(n) XOR operations and O(1) integer variables; with b-bit values, bit-level work is O(n*b) and the accumulator uses O(b) bits.

Common mistakes

XOR does not prove that the promised frequency pattern holds. Replacing XOR with OR prevents equal values from canceling.

Reasoning card

State: answer equals the XOR of all processed values. Its final value is determined by cancellation under the occurrence contract.

Invariant: Accumulator equals XOR of the processed prefix.

Decision to rehearse: Use x^x=0 and x^0=x.

Finish: Return the accumulator

Transfer exercise

Find two single values when every other value appears twice by partitioning on one set bit of their combined XOR.