Baseline Bit Manipulation · Interview Problems O(n) · O(1)
A sensor network logs ID pings in an audit trail where every sensor reports an even number of times except one faulty unit that reports an odd number. Rebuilding a tally table is overkill for the gateway firmware; instead it folds every ping ID through one accumulator, in which paired pings annihilate and the lone repeat-offender survives.
Input: An array arr of n positive integers where exactly one value occurs an odd number of times.
Output: The value with the odd occurrence count.
1 <= n <= 10^51 <= arr[i] <= 10^9Input: {"arr":[1,2,3,2,3,1,3]}
Output: 3
Pairs of 1s and 2s cancel; three 3s fold down to a lone survivor.
Input: {"arr":[5,5,5]}
Output: 5
One pair cancels and the third ping stands alone.