Single Number
Problem Description
Given a non-empty array of integers where every element appears twice except for one, find that single one. Must use O(1) extra space.
Example 1:
Input: nums = [2,2,1]
Output: 1
Example 2:
Input: nums = [4,1,2,1,2]
Output: 4
DE Shaw Tier 2 — LC 136.
Optimal: XOR all elements. a^a=0 and a^0=a, so pairs cancel and the single element remains.
Talk-track: 'XOR is commutative and associative — order doesn't matter. All pairs cancel to 0. The remaining value is the singleton.'
Example Test Cases
Example 1
Input: [[2,2,1]]
Expected: 1
Example 2
Input: [[4,1,2,1,2]]
Expected: 4
Example 3
Input: [[1]]
Expected: 1
Run your code to see the results