Skip to main content

XOR & Bitmask Sets

These problems push bits and XOR across a collection. XOR cancels duplicates (a ^ a = 0) and is a no-op against zero (a ^ 0 = a); a single integer can stand in for a set when the value range is small. Both ideas build on the foundational tricks.

XOR & Bitmask Sets
bits across a collection
XOR Tricks
a ^ a = 0, a ^ 0 = a
Fold
collapse a sequence
Invert
decode / prefix diff
Single Number
find what does not pair up
XOR cancels pairs
the loner survives
Bit counts mod 3
triples cancel
Set as Bitmask
an integer models a set
OR to add / test
mask |= (1 << x)
XOR to toggle parity
mask ^= (1 << x)
Index Marking
in-place presence bits
Mark seen
find missing / duplicates
+
−
⟲
⛶

XOR Tricks​

XOR is commutative and associative, so order never matters. That powers three moves: folding a sequence into one value, inverting an encoding (XOR is its own inverse), or complementing within a fixed bit width.

1486. XOR Operation in an Array​

Easy·
Solutions:
Visualize
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

2932. Maximum Strong Pair XOR I​

Easy·
Solutions:
Visualize
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

1720. Decode XORed Array​

Easy·
Solutions:
Visualize
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·
Solutions:
Visualize
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

1829. Maximum XOR for Each Query​

Medium·
Solutions:
Visualize
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

Single Number​

When every element pairs up except one, XOR is the sharpest tool: pairs annihilate and the loner falls out. The idea stretches to index-vs-value pairing, character ordinals, and parity bitmasks. When values repeat three times, XOR breaks down and we fall back to per-bit counting.

136. Single Number​

Easy·
Single Number
every other value appears twice
XOR Fold
pairs cancel, loner survives
O(1) space
one accumulator
Bitmask + log2
toggle a bit per value
Position = value
offset keeps it non-negative
+
−
⟲
⛶
Solutions:
Visualize
class Solution:
def singleNumber(self, nums: List[int]) -> int:
xor = 0
for number in nums:
xor = xor ^ number
return xor

540. Single Element in a Sorted Array​

Medium·
Solutions:
Visualize
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
xor = 0
for number in nums:
xor = xor ^ number
return xor

268. Missing Number​

Easy·
Missing Number
one value from 0..n is absent
XOR indices & values
everything cancels but the gap
O(1) space
single accumulator
Bitmask + log2
set present bits, negate, isolate
Sum formula
n(n+1)/2 - sum(arr)
No bit tricks
plain arithmetic
+
−
⟲
⛶
Solutions:
Visualize
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·
Find the Difference
t = shuffled s + one extra char
XOR ordinals
ord(char) pairs cancel
chr(xor)
recover the extra char
Bitmask + log2
toggle a bit per character
+
−
⟲
⛶
Solutions:
Visualize
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)

137. Single Number II​

Medium·
Solutions:
Visualize
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

266. Palindrome Permutation​

Easy·
Solutions:
Visualize
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

Set as Bitmask​

When the universe of values is small, a single integer models a set: bit x is set when element x is present. mask |= (1 << x) adds, mask & (1 << x) tests membership, and mask ^= (1 << x) toggles parity - all O(1), no hashing.

1684. Count the Number of Consistent Strings​

Easy·
Solutions:
Visualize
class Solution:
def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
count = len(words)
mask = 0
for i in allowed:
mask = mask | (1 << (ord(i) - ord("a")))
 
for word in words:
for i in word:
pos = 1 << (ord(i) - ord("a"))
if pos & mask == 0:
count -= 1
break
return count

2032. Two Out of Three​

Easy·
Solutions:
Visualize
class Solution:
def twoOutOfThree(
self, nums1: List[int], nums2: List[int], nums3: List[int]
) -> List[int]:
bm1 = bm2 = bm3 = 0
for i in nums1:
bm1 |= 1 << i
for i in nums2:
bm2 |= 1 << i
for i in nums3:
bm3 |= 1 << i
 
ans = []
for i in range(1, 101):
pos = 1 << i
if sum([bm1 & pos != 0, bm2 & pos != 0, bm3 & pos != 0]) >= 2:
ans.append(i)
return ans

2351. First Letter to Appear Twice​

Easy·
Solutions:
Visualize
class Solution:
def repeatedCharacter(self, s: str) -> str:
bitmap = 0
for i in s:
pos = 1 << (ord(i) - ord("a"))
if pos & bitmap:
return i
bitmap = bitmap | pos

2869. Minimum Operations to Collect Elements​

Easy·
Solutions:
Visualize
class Solution:
def minOperations(self, nums: List[int], k: int) -> int:
mask = (1 << k) - 1
mask <<= 1 # to incorporate 0th position
bitmap = 0
for i in range(len(nums) - 1, -1, -1):
bitmap = bitmap | (1 << nums[i])
if bitmap & mask == mask:
return len(nums) - i
return 0

2206. Divide Array Into Equal Pairs​

Easy·
Solutions:
Visualize
class Solution:
def divideArray(self, nums: List[int]) -> bool:
bitmask = 0
for i in nums:
bitmask = bitmask ^ (1 << i)
return bitmask == 0

2917. Find the K-or of an Array​

Easy·
Solutions:
Visualize
class Solution:
def findKOr(self, nums: List[int], k: int) -> int:
bitmask = 0
for pos in range(32):
bits = 0
for n in nums:
if n & (1 << pos):
bits += 1
if bits >= k:
bitmask = bitmask | (1 << pos)
return bitmask

In-Place Index Marking​

When values lie in [1, n], the array itself becomes the bitmask: mark presence in place (sign flip or a per-value bit) for O(1) auxiliary space instead of a hash set.

41. First Missing Positive​

Hard·
Solutions:
Visualize
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
def negate_bits(num: int) -> int:
bit_length = len(nums) + 2 # why + 2?
bitmask = (1 << bit_length) - 1 # binary with all 1's
return num ^ bitmask
 
bitmask = 0
for num in nums:
if num > 0 and num <= len(nums):
bitmask = bitmask | (1 << num)
 
negation = negate_bits(bitmask)
# zero is not a positive, hence unset 0 if set
negation = (negation | 1) ^ 1
# find the least significant set bit
ls_set = negation & -negation
 
return int(math.log2(ls_set))

448. Find All Numbers Disappeared in an Array​

Easy·
Solutions:
Visualize
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
def negate_bits(num: int) -> int:
bit_length = len(nums) + 1
bitmask = (1 << bit_length) - 1
return num ^ bitmask
 
bitmask = 0
for number in nums:
bitmask = bitmask | (1 << number)
 
negation = negate_bits(bitmask)
 
# 0 is not part of the range, ignore by unsetting it.
negation = (negation | 1) ^ 1
 
# append all those positions where a bit is set to 1
ans = []
for pos in range(negation.bit_length()):
if negation & (1 << pos):
ans.append(pos)
return ans

442. Find All Duplicates in an Array​

Medium·
Solutions:
Visualize
class Solution:
def findDuplicates(self, nums: List[int]) -> List[int]:
bitmask = 0
ans = []
for number in nums:
pos = 1 << number
# if the pos was already set, number has been already seen once
if bitmask & pos:
ans.append(number)
# set the position, which is number'th bit
bitmask = bitmask | pos
return ans