XOR Problems
XOR (^) has unique properties that make it extremely useful in coding problems. Key properties:
- a ^ a = 0
- a ^ 0 = a
- XOR is commutative and associative
- a ^ b ^ a = b
Example 1: Find the number that appears odd number of times
XOR all numbers; the result is the one that appears odd times because pairs cancel.
int result = 0;
for (int num : arr) result ^= num;
return result;
Example 2: Missing number in 1..n array
XOR all numbers 1..n and all array elements; duplicates cancel, leaving the missing number.
int xor = 0;
for (int i = 1; i <= n; i++) xor ^= i;
for (int num : arr) xor ^= num;
return xor;
Example 3: Swap two numbers without temporary variable
a = a ^ b;
b = a ^ b;
a = a ^ b;
Two Minute Drill
- XOR properties: a^a=0, a^0=a, commutative, associative.
- Useful for finding odd-occurrence elements, missing numbers, swapping.
- Often used in bit manipulation problems.
Need more clarification?
Drop us an email at career@quipoinfotech.com