Single Number

Difficulty: Easy · Topic: Bit manipulation

Every element in nums appears exactly twice except for one, which appears once. Return that single element using O(1) extra space. The trick: x ^ x = 0 and x ^ 0 = x, so XOR-ing everything cancels the pairs.

Examples

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

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

Target complexity: time O(n), space O(1)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.