Q3: Given an array where every element appears twice except one, how do you find the single number in O(n) time and O(1) space?
Use the properties of the bitwise XOR operator ($oplus$):
- $x oplus x = 0$ (Self-inverse)
- $x oplus 0 = x$ (Identity)
- $x oplus y = y oplus x$ (Commutative) XORing all elements across the array cancels out all paired numbers, leaving the single unique number.
Single Number XOR Solution
public class SingleNumber {
public static int findSingle(int[] nums) {
int result = 0;
for (int num : nums) {
result ^= num;
}
return result;
}
}💡 Accumulates XOR results across the array to isolate the un-paired value.
Key Takeaways
- XORing paired duplicate values reduces them to 0.
- Executes in $O(n)$ time with $O(1)$ auxiliary space.
Knowledge Check
What is the result of evaluating 5 ^ 3 ^ 5?