Coding Interview Patterns Module 17 – Bit manipulation
XOR tricks: unique and missing values
Find the value seen once, two unpaired values and a missing number with XOR: why equal values cancel, how one bit splits a pair, and when sums overflow.
What you will learn
- Find the value that appears once when every other value appears twice
- Separate two unpaired values with a bit on which they differ
- Find a missing number with XOR where a sum would overflow
- Prove the XOR solutions correct and write them in 14 languages
- Extend the idea to values seen three times, ranges of numbers and subarrays
Before you start
What you’ll learn · Before you start
What you will learn
- Find the value that appears once when every other value appears twice
- Separate two unpaired values with a bit on which they differ
- Find a missing number with XOR where a sum would overflow
- Prove the XOR solutions correct and write them in 14 languages
- Extend the idea to values seen three times, ranges of numbers and subarrays
Before you start
On this page
XOR (exclusive or): A bitwise operation that gives 1 where two bits differ and 0 where they are equal. x ^ x is 0, x ^ 0 is x, and the order of a chain of XORs does not change its result. finds the value without a partner. Two equal values cancel, because x ^ x is 0, and XOR
with 0 changes nothing, so the XOR of a whole list keeps only the values that appear an odd number of times, in
whatever order they come. When every value appears twice except one, a single pass with one integer returns that
value: O(n) time and O(1) extra memory, where counting needs a dictionary. The same cancellation finds two unpaired
values after one split on a bit where they differ, and a number missing from 0 to n without the sum that can
overflow a 32-bit integer.
Why equal values cancel
XOR compares two numbers bit by bit and keeps a 1 wherever they differ. On a single bit it is addition modulo 2, so the order and the grouping of a chain of XORs never change its result. Bit i of the XOR of a list is therefore 1 exactly when an odd number of the values have a 1 in bit i. A value that appears twice adds an even number to every column and leaves no trace:
The log 9, 14, 3, 9, 14, one bit column at a time
Text description of the diagram
The figure writes each tag of the log as four bits, worth 8, 4, 2 and 1. The tag 9 is 1001 and the tag 14 is 1110; both appear twice and are marked as pairs. The tag 3, 0011, appears once and is highlighted.
Under the five rows, each column's 1s are counted: the 8s column has 4, the 4s column 2, the 2s column 3 and the 1s column 3. The two copies of a paired tag always add an even number to a column, so only the tag seen once can make a count odd. The 2s and 1s columns are odd, so the XOR of the whole log is 0011, which is 3, the unpaired tag.
In the figure, the 1s and 2s columns hold three 1s each and the others an even number, so the XOR is 0011, the tag 3.
Checkpoint
Check: Why equal values cancel under XOR
The problem: the unpaired sock tag
The problem
A laundry sews a numbered tag into every sock and scans each tag when the washing comes back. Socks travel in pairs, so each tag is logged twice, except for one sock whose partner went missing. Return the tag that appears once. Limits: 1 ≤ n ≤ 2,000,001 entries, tags from 0 to 2³¹ − 1, and the log arrives as a stream that is read once, with O(1) extra memory.
[9, 14, 3, 9, 14]gives 3.[7]gives 7.[1001, 52, 52]gives 1001.
Two more questions use the same idea. Two socks may lose their partners, and then both tags are wanted, smaller first. And a train’s coaches, numbered 0 to n, may come back with one number missing from the yard’s list.
The brute force, and what it costs
Comparing each tag with the whole log needs no extra memory but up to n² looks, 4 × 10¹² at n = 2,000,001. Counting the tags in a dictionary takes one pass instead, but stores an entry for every distinct tag:
# The unpaired tag by brute force, two ways: compare every tag with the whole log (no extra memory, but n * n looks),
# or count the tags in a dictionary (one pass, but one entry for every distinct tag).
def unpaired_by_scanning(log):
"""For each tag, count its copies in the whole log: O(n^2) time, O(1) extra memory."""
looks = 0
for tag in log:
copies = 0
for other in log:
looks += 1
copies += other == tag
if copies == 1:
return tag, looks
raise ValueError("every tag has a partner")
def unpaired_by_counting(log):
"""Count every tag in a dictionary: O(n) time, O(n) extra memory."""
counts = {}
for tag in log:
counts[tag] = counts.get(tag, 0) + 1
lonely = [tag for tag, c in counts.items() if c == 1]
return lonely[0], len(counts)
for log in ([9, 14, 3, 9, 14], [7], [1001, 52, 52]):
tag, looks = unpaired_by_scanning(log)
_, entries = unpaired_by_counting(log)
print(f"{str(log):<18} unpaired {tag:>4} scanning: {looks:>2} looks dictionary: {entries} {'entry' if entries == 1 else 'entries'}")
n = 2_000_001
print(f"n = {n:,}: scanning takes up to {n * n:,} looks,")
print(f"and the dictionary holds {n // 2 + 1:,} entries")Output
[9, 14, 3, 9, 14] unpaired 3 scanning: 15 looks dictionary: 3 entries [7] unpaired 7 scanning: 1 looks dictionary: 1 entry [1001, 52, 52] unpaired 1001 scanning: 3 looks dictionary: 2 entries n = 2,000,001: scanning takes up to 4,000,004,000,001 looks, and the dictionary holds 1,000,001 entries
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 brute_force.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
On a seeded log of 2,000,001 tags, Python’s tracemalloc measured a peak of 60 MiB for the dictionary, against less
than 1 KiB for a running XOR:
# The memory the dictionary of counts needs for a log of 2,000,001 tags, measured with tracemalloc, against the one
# integer that a running XOR keeps. The log is random but seeded, so every run builds the same log.
import random
import tracemalloc
rng = random.Random(41)
pairs = 1_000_000
tags = rng.sample(range(2**31), pairs + 1)
log = tags * 2
log.pop() # the last tag keeps a single copy
rng.shuffle(log)
tracemalloc.start()
counts = {}
for tag in log:
counts[tag] = counts.get(tag, 0) + 1
lonely = next(tag for tag, c in counts.items() if c == 1)
dict_peak = tracemalloc.get_traced_memory()[1]
tracemalloc.stop()
entries = len(counts)
del counts
tracemalloc.start()
acc = 0
for tag in log:
acc ^= tag
xor_peak = tracemalloc.get_traced_memory()[1]
tracemalloc.stop()
print(f"log of {len(log):,} tags; the unpaired tag is {lonely:,}")
print(f"dictionary: {entries:,} entries, peak {dict_peak / 2**20:.0f} MiB of extra memory")
print(f"running XOR: {acc:,}, peak {'under 1 KiB' if xor_peak < 1024 else f'{xor_peak:,} bytes'} of extra memory")Output
log of 2,000,001 tags; the unpaired tag is 1,275,481,847 dictionary: 1,000,001 entries, peak 60 MiB of extra memory running XOR: 1,275,481,847, peak under 1 KiB of extra memory
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 dict_memory.py
Checkpoint
Check: What scanning and counting cost
The key idea: let the pairs cancel
XOR every tag into one integer that starts at 0. Each pair cancels wherever its two copies stand, so the integer ends as the unpaired tag. The running value in between means nothing on its own:
| Step | Tag | Running XOR | In binary |
|---|---|---|---|
| 1 | 9 | 9 | 1001 |
| 2 | 14 | 7 | 0111 |
| 3 | 3 | 4 | 0100 |
| 4 | 9 | 13 | 1101 |
| 5 | 14 | 3 | 0011 |
Step through the same pass and watch each second copy undo the first:
The drawing shows the whole scene; its 6 steps are listed below.
Every step as text
- Start at 0. The running value starts at 0, because XOR with 0 changes nothing. One integer is all the memory the pass needs, however long the log is.
- Tag 9. 0 ^ 9 is 9, which is 1001 in binary.
- Tag 14. 1001 and 1110 differ in bits 0, 1 and 2, so 9 ^ 14 is 0111, which is 7. The value in between means nothing on its own.
- Tag 3. 0111 ^ 0011 is 0100, which is 4.
- The second 9. 0100 ^ 1001 is 1101, which is 13. The two 9s have now both been XORed in, so they cancel, and 13 is 14 ^ 3.
- The second 14. 1101 ^ 1110 is 0011, which is 3. Both pairs have cancelled, so what is left is the tag that appears once.
Key idea
One integer, XORed with every tag in any order, ends as the tag without a partner, because each pair cancels to 0.
Checkpoint
Check: One pass of XOR over the log
Two unpaired tags: split on one bit
When tags a and b both appear once, the XOR of the log is a ^ b. It is not 0, because a and b differ, and each 1
in it marks a bit where they differ. The expression x & -x keeps the lowest set bit: The lowest bit of a number that is 1. In two's complement x & -x keeps exactly that bit: 12 is 1100, so 12 & -12 is 4. of
x, so 12 & -12 is 4. Split the log on that bit: both copies of a paired tag agree on it and stay together, while
a and b fall into different groups. XOR one group to get one answer, and XOR that with a ^ b to get the other.
For [12, 9, 12, 30, 7, 9] the XOR is 30 ^ 7, which is 25, or 11001 in binary, so the split bit is bit 0. The odd
tags 9, 9 and 7 give 7, and 25 ^ 7 gives 30. Step through the split:
The drawing shows the whole scene; its 9 steps are listed below.
Every step as text
- XOR of the log. The pairs 12 and 9 cancel, so the XOR of the whole log is 30 ^ 7, which is 11001 in binary, 25. It is not 0, because the two answers differ.
- Choose the bit. Each 1 in 11001 marks a bit where the two answers differ. The lowest is bit 0, which 25 & -25 = 1 finds, so the log is split by bit 0.
- 12. 12 is even, so its bit 0 is 0 and it goes to the second group.
- 9. 9 is odd, so it goes to the first group.
- The second 12. The second 12 has the same bit 0 as the first, so it lands in the same group and cancels it.
- 30. 30 is even, so it joins the second group.
- 7. 7 is odd, so it joins the first group, the group of the other answer.
- The second 9. The second 9 follows the first into the first group and cancels it, leaving 7.
- The two answers. Each group holds one answer, 7 and 30, and 25 ^ 7 = 30 confirms the second from the first. Smaller first, the answer is (7, 30).
Checkpoint
Check: Splitting two unpaired values on one bit
A missing number without a sum
The usual answer subtracts the list’s sum from n(n + 1)/2. In 32-bit integers the product n(n + 1) passes 2,147,483,647 from n = 46,341, while the answer is still small. XOR the numbers 0 to n with the list instead: every number present cancels against itself and the missing one is left, and no value on the way has more bits than n. Here it is on a small list:
The drawing shows the whole scene; its 6 steps are listed below.
Every step as text
- Two rows of numbers. On the left are the numbers 0 to 4 that should be there; on the right is the list of 4 numbers that came back. XOR all nine together.
- 3 cancels. The 3 of the list meets the 3 of 0 to 4, and 3 ^ 3 is 0, so the pair leaves no trace, wherever it stands in the order.
- 0 cancels. The 0 of the list cancels the 0 of 0 to 4.
- 4 cancels. The 4 cancels in the same way. No value on the way has more bits than 4, so there is nothing to overflow.
- 1 cancels. The 1 of the list cancels the 1 of 0 to 4.
- What is left. Only 2 has no partner, so the XOR of all nine numbers is 2, the missing number. The loop does the same with the indexes 0 to 3, starting its XOR at n = 4.
The same cancellation answers four more questions:
- Values seen three times: counting each bit modulo 3 finds the value seen once.
- A missing and a repeated number: one XOR and one split give both.
- The XOR of a range: the XOR of 0 to n repeats with period 4.
- Subarrays with a given XOR: prefix XORs and a dictionary count them in one pass.
Checkpoint
Check: The missing number from 0 to n
Practise: two unpaired IDs
Exercise · Medium · Python
The two unpaired IDs in constant memory
Write two_unpaired(ids). In ids, exactly two IDs appear once and every other ID appears exactly twice, in any order. Return the two IDs that appear once as a tuple, the smaller one first.
two_unpaired([12, 9, 12, 30, 7, 9]) # (7, 30)
two_unpaired([5, 8]) # (5, 8)
two_unpaired([-1, 2147483647, 5, 5]) # (-1, 2147483647)IDs are 32-bit signed integers, from −2,147,483,648 to 2,147,483,647, and there are at most 10⁶ of them. Use O(1) extra memory: a few integer variables, and no dictionary, set, Counter, sorted copy or other list built from ids. One sample test reads your code to check that, and another has a million IDs.
Starter code · two_unpaired.py
def two_unpaired(ids):
"""The two IDs that appear once in ids, smaller first; every other ID appears exactly twice."""
# Replace this line with your code.
return (0, 0)The sample tests · test_two_unpaired.py
import ast
import random
from collections import Counter
import two_unpaired as solution
from two_unpaired import two_unpaired
def brute(ids):
return tuple(sorted(i for i, c in Counter(ids).items() if c == 1))
def test_examples():
"""the three examples of the prompt"""
assert two_unpaired([12, 9, 12, 30, 7, 9]) == (7, 30)
assert two_unpaired([5, 8]) == (5, 8)
assert two_unpaired([-1, 2147483647, 5, 5]) == (-1, 2147483647)
def test_order_and_neighbours():
"""the smaller ID comes first, whatever order the log has, including IDs that differ in one bit"""
assert two_unpaired([8, 5]) == (5, 8)
assert two_unpaired([3, 2]) == (2, 3)
assert two_unpaired([0, 1, 4, 4]) == (0, 1)
assert two_unpaired([6, 6, 2, 4]) == (2, 4)
def test_ends_of_the_range():
"""IDs at both ends of the 32-bit range, and two IDs that differ only in the sign bit"""
assert two_unpaired([-2147483648, 2147483647]) == (-2147483648, 2147483647)
assert two_unpaired([-2147483648, 0, 7, 7]) == (-2147483648, 0)
assert two_unpaired([2147483647, -1, 2147483646, 2147483646]) == (-1, 2147483647)
def test_random_logs_against_counting():
"""1,500 random logs with negative and positive IDs, against counting with a Counter"""
rng = random.Random(17)
for _ in range(1500):
ids = rng.sample(range(-50, 50), rng.randint(2, 10))
log = ids[2:] * 2 + ids[:2]
rng.shuffle(log)
assert two_unpaired(log) == brute(log), f"two_unpaired({log})"
def test_a_million_ids():
"""1,000,000 IDs: 499,999 pairs and the two unpaired IDs"""
rng = random.Random(3)
ids = rng.sample(range(2**30), 500_001)
log = ids[2:] * 2 + ids[:2]
rng.shuffle(log)
assert two_unpaired(log) == tuple(sorted(ids[:2]))
def test_constant_extra_memory():
"""the function builds nothing from ids: no comprehensions, dict, set, Counter, sorted, list or slices"""
with open(solution.__file__, encoding="utf-8") as source:
tree = ast.parse(source.read())
used = []
for node in ast.walk(tree):
if isinstance(node, (ast.ListComp, ast.SetComp, ast.DictComp, ast.GeneratorExp, ast.Dict, ast.Set)):
used.append("a comprehension, dict or set")
elif isinstance(node, ast.Slice):
used.append("a slice")
elif isinstance(node, ast.Call) and getattr(node.func, "id", getattr(node.func, "attr", None)) in ("list", "dict", "set", "sorted", "Counter", "defaultdict", "tuple", "frozenset"):
used.append(f"{getattr(node.func, 'id', getattr(node.func, 'attr', ''))}()")
assert not used, "O(1) extra memory: remove " + ", ".join(sorted(set(used)))A hint
XOR every ID together first. Each pair cancels, so what is left is a ^ b for the two IDs you want, and it is not 0 because they are different. A bit that is 1 in a ^ b is a bit where a and b differ. How could that bit split the IDs into two groups, each with one of the two answers in it?
Results of the sample tests
| Test | Result | Details |
|---|
What your code printed
The sample tests run on this device, in your browser (Pyodide): nothing is sent to mysmartcopilot.com. The first run downloads Python (about 13.5 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.
These questions cover the ideas above, starting with the one you have answered least well.
Practice that adapts to you
Practise this lesson
13 questions about 9 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.
The three loops proved, in 14 languages, with the overflow traps Pro: opens with a Pro, Premium or Ultimate pass
Each loop rests on one fact that is easy to state and easy to break in a fixed-width language. Here each fact is proved, the three functions run in 14 languages, and the two overflow traps are reproduced.
In this part:
- Why the XOR of the log is the unpaired tag, proved column by column
- Why the split keeps every pair together, and why any differing bit works
- The three functions in 14 languages
- Checked against counting on 9,000 random logs
- The missing number in 32 bits: when the sum formula breaks, measured
1 diagram · 4 runnable examples (Python) · about 17 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Triples, a missing and a repeated number, ranges and subarrays, each run Pro: opens with a Pro, Premium or Ultimate pass
Each variant keeps the cancellation and changes what is counted. All four run below on original inputs, with the reason each works and the trap that comes with it.
In this part:
- Every other value three times: count each bit modulo 3
- One number missing and one repeated, from 1 to n
- XOR from 0 to n in O(1), and the XOR of a range
- Subarrays with a given XOR, from prefix XORs
- The variants and their traps
4 runnable examples (Python) · about 4 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Five plausible bugs reproduced, and a practice set with answers Pro: opens with a Pro, Premium or Ultimate pass
Most wrong XOR solutions come from a small change to a correct loop. Each bug below runs against a slow, obviously right answer until it fails, and a practice set follows.
In this part:
- Five bugs and the smallest inputs that break them
- A practice set with sample answers
1 runnable example (Python) · about 4 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Interview questions
-
Fresher to mid · Warm-up
Why does XORing every value of a list return the value that appears once, when every other value appears twice?
XOR works on each bit position separately, and on one bit it is addition modulo 2. So bit i of the XOR of the list is 1 exactly when an odd number of the values have a 1 in bit i. The two copies of a paired value add 0 or 2 to that count, which never changes whether it is odd, so only the unpaired value decides each bit, and the result equals it. The same facts in the usual form: x ^ x is 0, x ^ 0 is x, and the order and grouping of the XORs do not matter, so the pairs cancel wherever they stand. That is O(n) time and O(1) extra memory, with no dictionary.
-
Fresher to mid
Your Java two_unpaired passes every sample test but fails a hidden test where the two unpaired IDs are -1 and 2147483647. What goes wrong, and how do you write the split so that it works in Java, JavaScript, C++ and Go?
-
Mid to senior
A teammate finds the missing number of 0..n with n * (n + 1) / 2 minus the sum of the list, all in Java int. It passes a test with n = 100,000 but returns a huge negative number for n = 46,341. Explain both results, and say which fix you would ship.
-
Mid to senior
Sensor readings are 32-bit signed integers arriving as a stream. Every reading appears exactly three times except one, which appears once. With O(1) memory and one pass, how do you find the single reading, and how does the method change if every other reading appears k times?
Key takeaways
x ^ xis 0 andx ^ 0isx, in any order, so the XOR of a list keeps the values that appear an odd number of times.- One XOR pass finds the unpaired value in O(n) time and O(1) memory, where counting needs memory for every distinct value.
- Two unpaired values differ in at least one bit,
x & -xfinds one, and splitting the log on it separates them. - The XOR of 0 to n with the list finds a missing number without a sum that can overflow.
Terms in this lesson
- lowest set bit
- The lowest bit of a number that is 1. In two's complement x & -x keeps exactly that bit: 12 is 1100, so 12 & -12 is 4.
- XOR (exclusive or)
- A bitwise operation that gives 1 where two bits differ and 0 where they are equal. x ^ x is 0, x ^ 0 is x, and the order of a chain of XORs does not change its result.
References
- Bitwise operations on integer types (The Python Standard Library: built-in types) (Python Software Foundation)
- tracemalloc: trace memory allocations (The Python Standard Library) (Python Software Foundation)
- ECMAScript language specification: binary bitwise operators (Ecma International (TC39))
- The Java Language Specification, Java SE 25: 15.15.4 Unary minus operator (Oracle)
- The Java Language Specification, Java SE 25: 15.17.1 Multiplication operator (Oracle)
- Java SE 25 API: Integer.lowestOneBit (Oracle)
- Arithmetic operators: overflows (cppreference.com) (cppreference.com)
- UndefinedBehaviorSanitizer (Clang documentation) (LLVM Project)
- The Go Programming Language Specification: integer overflow (The Go Authors)
- The checked and unchecked statements (C# reference): the default overflow-checking context (Microsoft)
- Enumerable.Sum (.NET API): OverflowException when the sum is larger than Int32.MaxValue (Microsoft)
- ckd_add, ckd_sub and ckd_mul in C23 (cppreference.com) (cppreference.com)
- The Rust Reference: integer overflow (The Rust Project)
- Iterator::sum (Rust standard library): panics on overflow when overflow checks are on (The Rust Project)
- Primitive type i32 (Rust standard library): wrapping_neg (The Rust Project)
- The Swift Programming Language: advanced operators (overflow operators) (Swift.org)
- Java SE 25 API: IntStream.sum (Oracle)
- Integers (PHP manual): size and integer overflow (The PHP Group)
- Numbers in Dart (Dart (Google))
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress