Every element appears twice except one. Find the single one.

Interview question: Single Number

Given a non-empty array of integers `nums`, every element appears twice except for one. Find that single one.

Try to do it with linear runtime complexity and without using extra memory.

- 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).