Easy Bit Manipulation
Single Number
Receives an array of integers in which every value appears exactly twice except one, and returns that single unpaired value. It solves this with a single O(n) pass that XORs every element together: XOR is commutative and associative, and a value XORed with itself cancels to 0, so every duplicate pair cancels out and only the unpaired value survives in the running result. Returns that integer using no extra data structure — O(n) time, O(1) extra space.
Visualization
- Input
- Result
Algorithm code
// Single Number — a single pure function. Receives an array of integers where
// every value appears exactly twice except one, and returns that unpaired
// value. It XORs every element together: XOR is commutative and associative,
// and a value XORed with itself is 0, so every duplicate pair cancels out,
// leaving only the single element — O(n) time, O(1) extra space.
/**
* @param {number[]} arr - integers where every value appears twice except one
* @returns {number} the value that appears only once
*/
export function singleNumber(arr) {
let result = 0;
for (const value of arr) {
result ^= value;
}
return result;
}FUNCTION singleNumber(arr):
result ← 0
FOR EACH value IN arr:
result ← result XOR value
RETURN result