Single Number
Part of Practice: Counting & Canceling
You are given a non-empty array of integers nums. Every value in it appears exactly twice, except for one value that appears exactly once. Return that lone value.
The catch is in the follow-up: your solution must run in linear time and use only constant extra memory. That rules out the obvious "count everything in a hash map" answer, which needs memory proportional to the array size.
Examples
- Input:
- nums = [2, 2, 1]
- Output:
- 1
The two 2s pair up; 1 is the value with no partner.
- Input:
- nums = [4, 1, 2, 1, 2]
- Output:
- 4
1 and 2 each appear twice; only 4 appears once.
- Input:
- nums = [1]
- Output:
- 1
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.