Skip to main content

XOR

Three facts carry this entire page:

  • a ^ a = 0 - anything cancels itself
  • a ^ 0 = a - zero is the identity
  • XOR is commutative and associative - order never matters

Together they make XOR self-inverse: applying it twice returns the original. That is why it both destroys duplicates and undoes its own encoding, and why you can fold an array in any order and get the same answer in O(1) space.

Its one blind spot: XOR only tracks parity. When values repeat an odd number of times other than one, cancellation stops working and you fall back to counting each bit position separately, mod 3.

Cancellation​

Pairing values that should cancel exposes an imbalance even when it isn't a single repeated element: pair index against value to find a missing number, pair character ordinals across two strings, or keep a parity bitmask to test whether at most one character has an odd count. The same cancellation works with just two variables instead of a whole array: folding a value into its partner and unfolding it back out swaps them without a third variable to hold either one.

Swap The Numbers​

Basic·
2 Approaches
def solve(a, b):
a = a ^ b
b = a ^ b
a = a ^ b
return a, b

Detect If Two Integers Have Opposite Signs​

Basic·
def hasOppositeSigns(x, y):
return (x ^ y) < 0

268. Missing Number​

Easy·
4 Approaches · 3 patterns
FIG. 268 XOR● INTERACTIVE
visualization loads as you reach it
class Solution:
def missingNumber(self, nums: List[int]) -> int:
xor = len(nums)
for index in range(len(nums)):
xor = xor ^ index ^ nums[index]
return xor

389. Find the Difference​

Easy·
4 Approaches
FIG. 389 XOR● INTERACTIVE
visualization loads as you reach it
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
xor = 0
for char in s:
xor = xor ^ ord(char)
for char in t:
xor = xor ^ ord(char)
return chr(xor)

266. Palindrome Permutation​

Easy·
FIG. 266 PALINDROME PERMUTATION● INTERACTIVE
visualization loads as you reach it
class Solution:
def canPermutePalindrome(self, s: str) -> bool:
bitmask = 0
for char in s:
bitmask = bitmask ^ (1 << ord(char) - ord("a"))
return bitmask & (bitmask - 1) == 0 # check if bitmask has only one set bit

2206. Divide Array Into Equal Pairs​

Easy·
FIG. 2206 DIVIDE ARRAY INTO EQUAL PAIRS● INTERACTIVE
visualization loads as you reach it
class Solution:
def divideArray(self, nums: List[int]) -> bool:
bitmask = 0
for i in nums:
bitmask = bitmask ^ (1 << i)
return bitmask == 0

1506. Find Root of N-Ary Tree​

Medium·
3 Approaches · 2 patterns
FIG. FIND ROOT OF N ARY TREE 3● INTERACTIVE
visualization loads as you reach it
def findRoot(self, tree: List["Node"]) -> "Node":
xor = 0
for node in tree:
xor ^= node.val
for child in node.children:
xor ^= child.val
for node in tree:
if node.val == xor:
return node

Single Number​

When every element pairs up except one, XOR the whole array: the pairs annihilate and the loner falls out. The same trick extends past the basic case - a lone element in an otherwise-sorted array of pairs still XORs out, three copies instead of two needs counting each bit mod 3 rather than plain XOR, and two loners hiding among pairs separate cleanly once you isolate a bit where they differ.

136. Single Number​

Easy·
2 Approaches
FIG. 136 XOR● INTERACTIVE
visualization loads as you reach it
class Solution:
def singleNumber(self, nums: List[int]) -> int:
xor = 0
for number in nums:
xor = xor ^ number
return xor

One odd Occuring​

Basic·
FIG. ODD OCCURRENCE XOR● INTERACTIVE
visualization loads as you reach it
class Solution:
def getOddOccurrence(self, arr):
xor = 0
for i in arr:
xor ^= i
return xor

540. Single Element in a Sorted Array​

Medium·
FIG. 540 SINGLE ELEMENT IN A SORTED ARRAY● INTERACTIVE
visualization loads as you reach it
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
xor = 0
for number in nums:
xor = xor ^ number
return xor

137. Single Number II​

Medium·
3 Approaches
FIG. 137 SINGLE NUMBER II● INTERACTIVE
visualization loads as you reach it
class Solution:
def singleNumber(self, nums: List[int]) -> int:
"""Bit Manipulation: Mod 3"""
loner = 0
for pos in range(32):
bits = 0
for num in nums:
bits += num & (1 << pos) != 0
bits = bits % 3
loner = loner | (bits << pos)
# Do not mistaken sign bit for MSB.
if loner >= (1 << 31):
return loner - (1 << 32)
return loner

260. Single Number III​

Medium·
FIG. TWO SINGLE NUMBERS XOR MASK● INTERACTIVE
visualization loads as you reach it
def two_single_numbers(arr):
xor = 0
for i in arr:
xor ^= i
a = b = 0
mask = xor & (-xor)
for i in arr:
if i & mask:
a ^= i
else:
b ^= i
return [a, b]

Fold & Invert a Sequence​

Here XOR is used as a running accumulator rather than a duplicate-killer. Folding collapses a generated sequence into one value; inverting peels the original sequence back out of an encoded one, since encoded[i] = arr[i] ^ arr[i+1] rearranges to arr[i+1] = encoded[i] ^ arr[i]. Maximizing a XOR instead means choosing the partner whose high bits differ most.

1486. XOR Operation in an Array​

Easy·
FIG. 1486 XOR OPERATION IN AN ARRAY● INTERACTIVE
visualization loads as you reach it
class Solution:
def xorOperation(self, n: int, start: int) -> int:
xor = start
for i in range(1, n):
xor = xor ^ (start + 2 * i)
return xor

1720. Decode XORed Array​

Easy·
FIG. 1720 DECODE XORED ARRAY● INTERACTIVE
visualization loads as you reach it
class Solution:
def decode(self, encoded: List[int], first: int) -> List[int]:
ans = [first]
for i in encoded:
ans.append(ans[-1] ^ i)
return ans

2433. Find The Original Array of Prefix Xor​

Medium·
FIG. 2433 FIND THE ORIGINAL ARRAY OF PREFIX XOR● INTERACTIVE
visualization loads as you reach it
class Solution:
def findArray(self, pref: List[int]) -> List[int]:
ans = [pref[0]]
for i in range(1, len(pref)):
ans.append(pref[i - 1] ^ pref[i])
return ans

2683. Neighboring Bitwise XOR​

Medium·
3 Approaches
FIG. 2683 INVERT PREFIX● INTERACTIVE
visualization loads as you reach it
class Solution:
def doesValidArrayExist(self, derived: List[int]) -> bool:
original = [0]
for i in range(len(derived)):
original.append(original[i] ^ derived[i])
return original[0] == original[-1]

1829. Maximum XOR for Each Query​

Medium·
FIG. 1829 MAXIMUM XOR FOR EACH QUERY● INTERACTIVE
visualization loads as you reach it
class Solution:
def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:
xor = 0
ans = []
for i in nums:
xor = xor ^ i
ans.insert(0, xor ^ (2**maximumBit - 1))
return ans

2932. Maximum Strong Pair XOR I​

Easy·
FIG. 2932 MAXIMUM STRONG PAIR XOR I● INTERACTIVE
visualization loads as you reach it
class Solution:
def maximumStrongPairXor(self, nums: List[int]) -> int:
maxi = 0
for i in nums:
for j in nums:
if abs(i - j) <= min(i, j):
maxi = max(maxi, i ^ j)
return maxi