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 Approachesclick to switch
Explanation

XOR is self-inverse: a ^ a = 0 and a ^ 0 = a. After a = a ^ b, a holds the combined bits of both numbers. XOR-ing that combined value with b recovers the original a, so b = a ^ b sets b to the original a. XOR-ing again with the new b (the original a) strips it back out of the combined value, so a = a ^ b leaves a holding the original b. Three XORs, no third variable.

Analysis
Time
O(1)
  • Three XOR operations regardless of input size.
Space
O(1)
  • No extra variable is used to hold either number.
FIG. SWAP THE NUMBERS XOR● INTERACTIVE
visualization loads as you reach it
def solve(a, b):
a = a ^ b
b = a ^ b
a = a ^ b
return a, b

Detect If Two Integers Have Opposite Signs​

Basic·
Explanation

In two's complement, the sign bit (the most significant bit) is 1 for a negative number and 0 for a non-negative one. XOR-ing two numbers sets that bit only when the operands' sign bits differ, and any value with its sign bit set is negative - so x ^ y is negative exactly when x and y have opposite signs.

Analysis
Time
O(1)
  • A single XOR and comparison regardless of input size.
Space
O(1)
  • No extra storage beyond the two inputs.
FIG. OPPOSITE SIGNS XOR● INTERACTIVE
visualization loads as you reach it
def hasOppositeSigns(x, y):
return (x ^ y) < 0

268. Missing Number​

Easy·
3 Approachesclick to switch
Explanation

The array holds n distinct numbers drawn from 0, 1, ..., n. Seed the accumulator with n, then XOR in every index together with its value. Each number that is present appears once as an index and once as a value and cancels itself; the one missing number never gets cancelled and survives.

For [3, 0, 1]: 3 ^ (0^3) ^ (1^0) ^ (2^1) collapses to 2.

Analysis
Time
O(N)
  • One pass XOR-ing each index and value.
Space
O(1)
  • A single accumulator.
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 Approachesclick to switch
Explanation

String t is a shuffle of s with one extra character. Treat each character as its code point and XOR every code from both strings together. Each shared character contributes its code twice and cancels (a ^ a = 0), so the surviving value is the code point of the added character. chr turns it back into the answer.

Analysis
Time
O(2n)
  • Two separate linear passes - one XOR fold over s (n characters), one over t (n + 1 characters) - each O(n), giving 2n, where n = len(s).
Space
O(1)
  • A single accumulator.
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·
Explanation

A string can be rearranged into a palindrome when at most one character has an odd count. We track parity, not full counts: toggle the bit at position ord(char) - ord("a") for every character. A character seen an even number of times ends with its bit at 0; an odd number of times leaves it 1.

At the end, bitmask & (bitmask - 1) == 0 is true only when at most one bit is set - i.e. zero or one character has an odd count - which is exactly the palindrome condition.

Analysis
Time
O(N)
  • One toggle per character in the string.
Space
O(1)
  • A single integer bitmask.
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·
Explanation

The array can be split into equal pairs only if every value appears an even number of times. XOR is the perfect parity tracker: toggling bit i with bitmask ^= (1 << i) for each value i flips that bit on every occurrence.

If every value occurs an even number of times, all bits cancel back to 0. So the array is pairable exactly when the final bitmask == 0.

Analysis
Time
O(N)
  • One pass toggling bits.
Space
O(1)
  • A single integer mask (value range up to 500 bits).
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

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 Approachesclick to switch
Explanation

XOR is commutative and associative, with two key identities: a ^ 0 = a and a ^ a = 0. So XOR-ing the entire array makes every value that appears twice cancel itself out, leaving only the unique number:

a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b

For [4, 1, 2, 1, 2] every pair cancels and 4 remains.

Analysis
Time
O(n)
  • n = len(nums). One XOR into xor per element in a single pass.
Space
O(1)
  • Only the xor accumulator is kept; nothing scales with n.
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·
Explanation

XOR is commutative and associative, with two key identities: a ^ 0 = a and a ^ a = 0. XOR-ing the entire array cancels every value that occurs an even number of times, no matter how many times it repeats, and leaves only the value that occurs an odd number of times.

Analysis
Time
O(N)
  • One XOR per element in a single pass.
Space
O(1)
  • A single accumulator variable.
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·
Explanation

Although the array is sorted, the same cancellation trick from 136. Single Number applies directly: every value appears twice except one, and XOR-ing the whole array makes the paired values cancel (a ^ a = 0), leaving the unique element.

The sorted order enables a faster O(log n) binary search, but this XOR fold is the simplest correct solution.

Analysis
Time
O(N)
  • One XOR per element across the array.
Space
O(1)
  • A single accumulator.
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 Approachesclick to switch
Explanation

Here every value appears three times except one. Plain XOR no longer works, so count instead. For each of the 32 bit positions, sum how many numbers have that bit set. Bits contributed by the tripled values sum to a multiple of 3; taking the count mod 3 leaves only the contribution of the lone number, which we OR back into the result.

A signed-integer guard fixes the sign bit: if the rebuilt value has bit 31 set, it represents a negative number in two's complement, so we subtract 2 ** 32.

Analysis
Time
O(n)
  • 32 fixed bit positions, each scanning all n numbers - linear in n.
Space
O(1)
  • A constant number of integer accumulators.
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·
Explanation

XOR the whole array first: every paired value cancels, leaving xor = a ^ b for the two lone numbers. a and b must differ in at least one bit, so mask = xor & (-xor) isolates the lowest bit where they differ. Splitting arr by whether each element has that bit set separates a from b into two independent single-number groups, each of which collapses under XOR to one of the answers.

Analysis
Time
O(2N)
  • Two separate O(n) passes over arr: one to build xor, one to split by mask - 2n.
Space
O(1)
  • Only xor, mask, a, and b are stored.
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·
Explanation

The array is defined implicitly: element i is start + 2 * i. Instead of materializing it, we fold the XOR as we go.

Seed the accumulator with the first element (start), then XOR in each subsequent term start + 2 * i for i from 1 to n - 1. Because every term differs from its neighbour by a constant 2, no extra storage is needed - the running value carries all the information.

Analysis
Time
O(n)
  • The for i in range(1, n) loop folds n - 1 terms into xor in a single pass - O(n).
Space
O(1)
  • Only the running xor value is stored.
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·
Explanation

The encoding rule is encoded[i] = arr[i] ^ arr[i + 1]. XOR is its own inverse, so XOR-ing both sides by arr[i] recovers the next element:

arr[i + 1] = encoded[i] ^ arr[i]

Starting from the known first, each step XORs the latest decoded value with the next encoded entry to peel off the following original element.

Analysis
Time
O(N)
  • One XOR per encoded element rebuilds the original array.
Space
O(N)
  • The output array holds all n + 1 decoded elements.
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·
Explanation

pref[i] is the running XOR of the original array up to index i, so pref[i] = arr[0] ^ ... ^ arr[i]. Consecutive prefixes differ by exactly one element:

pref[i] = pref[i - 1] ^ arr[i] ⇒ arr[i] = pref[i - 1] ^ pref[i]

The first element is just pref[0]. For every later index, XOR-ing adjacent prefix values cancels the shared history and leaves the single original element.

Analysis
Time
O(N)
  • One XOR of adjacent prefixes per element.
Space
O(N)
  • The reconstructed array holds n elements.
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 Approachesclick to switch
Explanation

derived[i] = original[i] ^ original[i + 1] (indices wrap for the last element). Seed original = [0] and invert the recurrence one step at a time: original[i + 1] = original[i] ^ derived[i]. Since the array wraps, original[len(derived)] should equal the seed original[0] if and only if a valid original exists - any other outcome means the wraparound XOR doesn't cancel out.

Analysis
Time
O(N)
  • One pass building original from derived.
Space
O(N)
  • The reconstructed original array holds n + 1 elements.
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·
Explanation

Each query removes the last element, so it asks for the XOR of a shrinking prefix. We process the elements left to right while keeping the running XOR of everything seen so far.

To maximize xor ^ k, pick the k that flips every bit of xor within the allowed maximumBit width - that is the all-ones mask 2 ** maximumBit - 1. XOR-ing the running value with that mask gives the answer for the current prefix. Because queries are answered in reverse order of array length, each result is inserted at the front.

Analysis
Time
O(n^2)
  • The for i in nums loop runs n times, where n = len(nums), and each iteration's XOR update is O(1).
  • ans.insert(0, ...) shifts every existing element of ans to make room at the front, which is O(i) on the i-th call; summed across all n calls that is O(n^2).
Space
O(n)
  • ans holds one value per query, up to n entries.
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·
Explanation

A pair (i, j) is strong when abs(i - j) <= min(i, j). With the small constraints of this version, we simply try every ordered pair, keep only those that satisfy the strong condition, and track the largest XOR seen.

The double loop reuses each element as both endpoints, so self-pairs (i == j) are also considered - their XOR is 0 and never beats a real maximum.

Analysis
Time
O(n²)
  • n is the length of nums - the nested for i in nums: for j in nums: loops examine every ordered pair.
Space
O(1)
  • Only the running maxi is stored, regardless of array length.
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