Single Number (Appears Once)

Finding the one element that appears once while everything else appears twice, via nested loops, a hashmap, or XOR.

Every element appears twice except one — find it. [1,1,2,3,3,4,4] → 2. (LeetCode 136)

Brute force: for each element, count its occurrences via a nested scan — O(n²).

Better — hashmap: count frequencies, then find the key with count 1 — O(n) time, O(n) space.

Optimal — XOR: a ^ a = 0, so XOR-ing every element cancels every pair, leaving only the single value.

xor = 0;
for(int i = 0; i < n; i++) xor = xor ^ arr[i];
return xor;

Time: O(n). Space: O(1).