15. Single Number (XOR Trick)

Given a non-empty array of integers nums, every element appears exactly twice except for one.

Find and return that single one.

You must implement a solution with O(n) time complexity and O(1) extra space.

Input: An integer array nums where every element appears twice except one.

Output: A single integer — the element that appears only once.

Examples

Example 1

Input: [2,2,1]
Output: 1
Explanation: XOR all: 2^2^1 = 0^1 = 1. Pairs cancel to 0. The lonely element remains. Return 1.

Example 2

Input: [4,1,2,1,2]
Output: 4
Explanation: 1^1=0, 2^2=0. 4^0^0=4. Return 4.

Example 3

Input: [1]
Output: 1
Explanation: Only one element — no pair. Return 1.