Single Number

Best Time to Buy and Sell Stock

Move Zeroes

Find the only value that is not paired using constant extra space.

Every value in `nums` appears exactly twice except one value that appears once. Return the unpaired value.

**Input / output**
- Input: `nums: integer[]`
- Output: the unique integer

**Examples**
1. `[2,2,1]` returns `1`.
2. `[4,1,2,1,2]` returns `4`.

**Constraints**
- `1 <= nums.length <= 100,000`
- `nums.length` is odd
- The input satisfies the pairing rule

**Follow-up**
Why does XOR remove paired values regardless of their order?

- Every value appears exactly twice except one value.
- We need to return the value that appears once.
- The challenge asks for linear time and no extra memory.

Understand the Pattern

- A dictionary can count how many times each number appears.
- Then we return the number with count `1`.
- This is O(n) time, but it uses O(n) extra space.

Counting Approach

- XOR has useful properties: `x ^ x = 0` and `x ^ 0 = x`.
- XOR is also commutative, so order does not matter.
- When all numbers are XORed together, paired values cancel and only the single value remains.

Key Insight: XOR Cancels Pairs

- Start with `result = 0`.
- XOR every number into `result`.
- After the loop, `result` is the number that appeared once.

Accumulate with XOR

- The XOR solution meets the follow-up requirement.
- Time complexity is O(n).
- Space complexity is O(1).