XOR Problems
In this page:
XOR Property
XOR has two properties that make it especially useful in puzzles: any value XORed with itself is zero (a ^ a = 0), and any value XORed with zero stays unchanged (a ^ 0 = a) — together these let matching pairs cancel out completely.
Example: XOR Property
#include <iostream>
using namespace std;
int main() {
int a = 7;
cout << "a^a=" << (a^a) << " a^0=" << (a^0) << " -- self-cancels to 0, identity with 0 unchanged";
return 0;
}public class Main {
public static void main(String[] args) {
int a = 7;
System.out.println("a^a=" + (a^a) + " a^0=" + (a^0) + " -- self-cancels to 0, identity with 0 unchanged");
}
}a = 7
print(f"a^a={a^a} a^0={a^0} -- self-cancels to 0, identity with 0 unchanged")#include <stdio.h>
int main() {
int a = 7;
printf("a^a=%d a^0=%d -- self-cancels to 0, identity with 0 unchanged", a^a, a^0);
return 0;
}Login to try C/C++/Java code in the editor
Find Single Number
If every number in an array appears exactly twice except for one number that appears only once, XOR-ing every element together cancels out all the duplicate pairs, leaving only the single unmatched number as the result.
Example: Find Single Number
#include <iostream>
using namespace std;
int main() {
int arr[] = {4,1,2,1,2};
int result = 0;
for (int x : arr) result ^= x;
cout << "Duplicate pairs cancel, single number left: " << result;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {4,1,2,1,2};
int result = 0;
for (int x : arr) result ^= x;
System.out.println("Duplicate pairs cancel, single number left: " + result);
}
}arr = [4,1,2,1,2]
result = 0
for x in arr:
result ^= x
print("Duplicate pairs cancel, single number left:", result)#include <stdio.h>
int main() {
int arr[] = {4,1,2,1,2};
int result = 0;
for (int i = 0; i < 5; i++) result ^= arr[i];
printf("Duplicate pairs cancel, single number left: %d", result);
return 0;
}Login to try C/C++/Java code in the editor
Missing Number
When an array is supposed to contain every number from 0 to n but is missing exactly one, XOR-ing all the array's numbers together with all the numbers from 0 to n cancels out every number that's present in both, leaving the missing one behind.
Example: Missing Number
#include <iostream>
using namespace std;
int main() {
int arr[] = {0,1,3,4}, n = 4;
int result = n;
for (int i = 0; i < n; i++) result ^= i ^ arr[i];
cout << "Missing number: " << result;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {0,1,3,4};
int n = 4;
int result = n;
for (int i = 0; i < n; i++) result ^= i ^ arr[i];
System.out.println("Missing number: " + result);
}
}arr = [0,1,3,4]
n = 4
result = n
for i in range(n):
result ^= i ^ arr[i]
print("Missing number:", result)#include <stdio.h>
int main() {
int arr[] = {0,1,3,4}, n = 4;
int result = n;
for (int i = 0; i < n; i++) result ^= i ^ arr[i];
printf("Missing number: %d", result);
return 0;
}Login to try C/C++/Java code in the editor
Swap Using XOR
Two integer variables can be swapped without a temporary variable using three XOR operations in sequence (a ^= b; b ^= a; a ^= b;), relying entirely on XOR's self-cancelling and identity properties rather than an extra storage slot.
Example: Swap Using XOR
#include <iostream>
using namespace std;
int main() {
int a = 5, b = 9;
a ^= b; b ^= a; a ^= b;
cout << "Swapped without a temp variable: a=" << a << " b=" << b;
return 0;
}public class Main {
public static void main(String[] args) {
int a = 5, b = 9;
a ^= b; b ^= a; a ^= b;
System.out.println("Swapped without a temp variable: a=" + a + " b=" + b);
}
}a, b = 5, 9
a ^= b
b ^= a
a ^= b
print(f"Swapped without a temp variable: a={a} b={b}")#include <stdio.h>
int main() {
int a = 5, b = 9;
a ^= b; b ^= a; a ^= b;
printf("Swapped without a temp variable: a=%d b=%d", a, b);
return 0;
}Login to try C/C++/Java code in the editor
XOR Practice
XOR-based tricks are popular in interview problems specifically because they solve tasks that would normally need extra memory (like a hash set to track duplicates) using only constant extra space, thanks to how cleanly duplicate values cancel out.
Example: XOR Practice
#include <iostream>
using namespace std;
int main() {
cout << "XOR tricks solve dedup-style tasks with O(1) extra space instead of a hash set";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("XOR tricks solve dedup-style tasks with O(1) extra space instead of a hash set");
}
}print("XOR tricks solve dedup-style tasks with O(1) extra space instead of a hash set")#include <stdio.h>
int main() {
printf("XOR tricks solve dedup-style tasks with O(1) extra space instead of a hash set");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 5 topics to unlock
0/5 topics done
Complete these topics first: