Single Number algorithm explained step-by-step: bitwise XOR mathematical properties (A ^ A = 0, A ^ 0 = A), linear scan without auxiliary memory, and JavaScript implementation.
Given a non-empty array of integers where every element appears exactly twice except for one unique element, find that single element in O(n) linear time without allocating extra heap memory.
While hash sets or hash tables solve this in O(n) space, bitwise XOR (^) solves it in strictly O(1) auxiliary space by exploiting three fundamental mathematical properties: Commutativity (a ^ b = b ^ a), Associativity ((a ^ b) ^ c = a ^ (b ^ c)), and Self-Inverse (a ^ a = 0 and a ^ 0 = a). XORing all elements together cancels every duplicate pair, directly isolating the single unique value.
Set `result = 0`. By the identity `0 ^ x = x`, initializing with 0 will not alter the computation.
For each integer `num` in the array, perform `result ^= num`.
Because XOR is commutative and associative, elements can be mentally rearranged into pairs: `(x1 ^ x1) ^ (x2 ^ x2) ^ ... ^ unique = 0 ^ 0 ^ ... ^ unique = unique`.
After the loop finishes, `result` holds the exact single unrepeated number.
1function singleNumber(nums) {2 let result = 0;3 for (const num of nums) {4 result ^= num; // Bitwise XOR5 }6 return result;7}8 9// Example usage:10// singleNumber([4, 1, 2, 1, 2]); // Returns 411//12// Step-by-step Bitwise evaluation:13// 0 ^ 4 = 414// 4 ^ 1 = 515// 5 ^ 2 = 716// 7 ^ 1 = 6 (1 cancels previous 1)17// 6 ^ 2 = 4 (2 cancels previous 2)18// Final result: 4Play through every comparison, swap, and state change, adjust the speed, or enter custom inputs to test edge cases.
The full interactive roadmap is unlocking — these specialized modules land in upcoming releases.
This feature will be implemented in the next update.
This feature will be implemented in the next update.
This feature will be implemented in the next update.
Explore the full catalog — 30+ algorithms with more unlocking every release.
Bitwise operator & binary bit manipulation inspector
Test your understanding of Single Number (Bitwise XOR) complexity and step mechanics.
Q1.What is the value of x ^ x for any integer x?
Q2.What happens if we apply XOR to an array where two different elements appear once and all others appear twice?
Apply Single Number (Bitwise XOR) to real coding interview questions.
Find the element that appears once in linear runtime O(n) and O(1) extra space.
Given an array containing n distinct numbers in the range [0, n], return the only number missing from the range.