XOR Problems

XOR is like a game where two matching things cancel each other out, so when everything is paired up except one, only the odd one out is left.

In this page:

XOR Property
Find Single Number
Missing Number
Swap Using XOR
XOR Practice

Syntax

markup

result = 0
for x in arr:
    result ^= x    # pairs cancel out
# result holds the single number

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;
}

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;
}

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;
}

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;
}

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;
}

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Power of Two Next Lesson → Top Array and String Problems