THE BIT STRIP
Underneath every integer is 32 switches. This deck teaches you to reach for them: read, set, clear and toggle a single bit, count them with a trick, enumerate every subset with a bitmask, and lean on the one identity that carries the whole topic — a ^ a = 0. Every operator runs live on a 32-cell strip you can step and predict, and each concept lecture is wrapped: prime it, watch it, drill it, then solve the sheet problems it unlocks.
This is not a list of problems. It is 11 learning units, and every one runs the same four beats. Go in order and the problems stop feeling random.
ASSUMEDA binary trie in unit 09, tagged beyond the sheet. Tries is step 17 and not built yet, so that unit builds one from nothing.
16 PROBLEMS · EVERY ONE LINKS TO LEETCODE TO SOLVE
Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the sheet's row, not your position — the deck teaches in the order that builds, so you will meet them slightly out of numerical sequence.
Bit manipulation is a small box of tools, each triggered by a specific phrase in the statement. The cards are the cues — “exactly one bit”, “twice except one”, “all subsets” — and the one-line trick each one licenses.
a power of two has a single 1 bit, so n & (n-1) wipes it to zero
n > 0 && (n & (n-1)) == 0O(1)walk the set bits with n & (n-1), or the 32 positions once each
KERNIGHAN COUNT · PER-BIT PASSO(1) per numbera ^ a = 0, so XOR-ing everything cancels the pairs and leaves the odd one
XOR SWEEPO(n) time · O(1) spacean n-bit mask IS a subset; count 0..2ⁿ-1 to enumerate them
BITMASK ENUMERATIONO(2ⁿ · n)insert 32-bit numbers into a trie, then greedily take the opposite bit
BINARY TRIE + GREEDY WALKO(n · 32)rebuild arithmetic from shifts: carry is (a & b) << 1, quotient doubles the divisor
SHIFT-AND-ADDO(log n)The word is 32 bits, so any per-bit pass is a constant — that is why counting or reversing a number is O(1). Small n (≤ ~20) says “enumerate subsets with a bitmask”; a big array says “one XOR sweep”.
32-BIT WORD ⇒ PER-BIT WORK IS O(1) · n ≤ 20 ⇒ BITMASK · BIG ARRAY ⇒ XOR SWEEP
Eleven units. The first five own a Striver lecture and a live bit-strip; the XOR family is the heart of the topic, and the last two (Max XOR via a trie, and the Advanced-Maths pair) go a step beyond the sheet.
The one identity the whole XOR half of this deck rests on: what are x ^ x and x ^ 0?
x ^ x = 0, x ^ 0 = x. XOR is 1 only where the two bits differ, so a number XOR-ed with itself is all-zeros, and XOR-ed with zero is unchanged. Add associativity and commutativity and XOR-ing a whole array makes every duplicate annihilate its partner in any order — the survivor is whatever appears an odd number of times. Single Number, Missing Number and Single Number III are all this one fact.
Read the bits: what is 1 << 4 as a decimal, and which bit position does it set?
16 = 0001 0000, bit 4. Left-shifting 1 by i slides the single set bit up to position i, and its value is 2ⁱ. That shifted 1 is the mask every single-bit operation starts from: AND it to read, OR it to set, AND with its complement to clear, XOR it to toggle.
Every integer is a row of 32 switches, and every bit problem is built from four moves on them. Build a mask with 1 << i — a single 1 in position i — then combine it with n: AND reads the bit, OR sets it, AND with ~mask clears it, XOR toggles it. Odd/even is just bit 0; a power of two is a single set bit; and counting the 1s is one loop of n & (n-1). Own these and the rest of the deck is composition.
HOW DO YOU READ, FLIP OR COUNT A SINGLE BIT INSIDE A NUMBER?
To test whether bit i of n is set, which expression is correct?
(n & (1<<i)) != 0. 1<<i is a mask with a single 1 in position i; ANDing keeps only that bit of n, so the result is non-zero precisely when the bit is set. n & i is meaningless (it ANDs with the index), and n | (1<<i) would set the bit rather than read it. Equivalently, (n >> i) & 1 shifts the bit down to position 0 and masks it.
n = 13 is 1101. What is n & (n - 1), and what did the operation do?
12 (1100) — the lowest 1 is gone. n - 1 = 12 = 1100 flips bit 0 to 0; ANDing 1101 & 1100 = 1100 = 12. That is exactly one set bit removed. Do it again on 12 and you get 8, then 0 — three steps for three set bits, which is why Kernighan's count loops once per 1 rather than 32 times. The visualiser strikes out the vanishing bit at each step.
This “is n a power of two?” check returns true for n = 0, which is wrong. Which line is the bug?
1 bool isPowerOfTwo(int n) {
2 return (n & (n - 1)) == 0;
3 }
Line 2 needs n > 0 &&. The (n & (n-1)) == 0 test is true for any number with at most one set bit — and zero has no set bits, so it slips through. Powers of two are strictly positive, so guard with n > 0. (Negatives in two's complement also fool the bare test, and the guard rules them out too.)
Every single-bit operation is the same two-step move: build a mask with a 1 in position i using 1 << i, then combine it with n. AND reads (n & mask), OR sets (n | mask), AND with NOT clears (n & ~mask), and XOR toggles (n ^ mask). Learn to see the mask sliding to position i and the four operators become one idea with four verbs — the primitives every other problem in the deck is built from.
The naive count checks all 32 bits; Brian Kernighan's trick checks only the set ones. n - 1 flips the lowest set bit to 0 and every 0 below it to 1; ANDing that back with n wipes exactly that lowest set bit and leaves the rest untouched. Repeat until n is 0 and you've looped once per set bit — so a number with three 1s costs three iterations, not 32. Watch the rightmost 1 vanish each step; that disappearing bit is the whole algorithm.
“Is n a power of two?” A power of two is exactly one set bit, and one set bit is the signature of the n & (n-1) trick.
A power of two in binary is a single 1 followed by zeros (1, 10, 100, …). Clearing its lowest set bit with n & (n-1) therefore leaves exactly zero. Guard n > 0 first, because zero and negatives also make the bare test true.
// Exactly one set bit, and strictly positive. bool isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }
// Exactly one set bit, and strictly positive. public boolean isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }
# Exactly one set bit, and strictly positive. def isPowerOfTwo(n): return n > 0 and (n & (n - 1)) == 0
Dropping the n > 0 guard. (n & (n-1)) == 0 is also true for n = 0 (no set bits) and misbehaves for negatives in two's complement — both would be wrongly reported as powers of two. The positivity check is not optional.
“Count the 1 bits (Hamming weight).” Counting set bits is the textbook use of Kernighan's n & (n-1) loop.
Instead of testing all 32 positions, repeatedly clear the lowest set bit with n & (n-1) and count how many times you can before n hits zero. Each iteration removes exactly one 1, so the loop runs once per set bit — cheap for sparse numbers.
// Kernighan: strip the lowest set bit each loop. int hammingWeight(uint32_t n) { int count = 0; while (n != 0) { n = n & (n - 1); // drop the lowest set bit count++; } return count; }
// Kernighan: strip the lowest set bit each loop. public int hammingWeight(int n) { int count = 0; while (n != 0) { n = n & (n - 1); // drop the lowest set bit count++; } return count; // Java has no unsigned; the loop ends anyway }
# Kernighan: strip the lowest set bit each loop. def hammingWeight(n): count = 0 while n: n &= n - 1 # drop the lowest set bit count += 1 return count
Looping a fixed 32 times, or using a signed shift. The fixed loop works but the Kernighan version is proportional to the set bits, not the word size. If you do shift instead, use an unsigned type — an arithmetic right shift of a negative int keeps feeding in 1s and never terminates.
“Return the set-bit count for every number 0..n.” The ‘for every i’ plus a cheap relation to a smaller value is a DP-on-bits cue.
Don't count each number from scratch. i has the same set bits as i >> 1 plus one more if i is odd. So dp[i] = dp[i >> 1] + (i & 1) — every answer is built from a smaller, already-computed one in O(1).
// dp[i] = dp[i>>1] + (i&1): reuse the smaller answer. vector<int> countBits(int n) { vector<int> dp(n + 1, 0); for (int i = 1; i <= n; i++) dp[i] = dp[i >> 1] + (i & 1); return dp; }
// dp[i] = dp[i>>1] + (i&1): reuse the smaller answer. public int[] countBits(int n) { int[] dp = new int[n + 1]; for (int i = 1; i <= n; i++) dp[i] = dp[i >> 1] + (i & 1); return dp; }
# dp[i] = dp[i>>1] + (i&1): reuse the smaller answer. def countBits(n): dp = [0] * (n + 1) for i in range(1, n + 1): dp[i] = dp[i >> 1] + (i & 1) return dp
Recomputing each count independently. Calling an O(32) popcount for every i is O(32n) and misses the point. The whole value here is the recurrence: i >> 1 is a strictly smaller index whose answer you already have, so one lookup plus the parity bit finishes it in O(1).
This lecture is a bag of identities worth memorising outright, each replacing a loop with one line. Swap without a temp — three XORs, because every XOR is its own undo. Isolate the lowest set bit with n & -n (two's-complement negation flips everything above the lowest 1, so ANDing keeps only that bit). Strip the lowest set bit with n & (n-1). And reverse a word by pulling bits off one end and pushing them onto the other. Each is a reflex you compose later.
WHICH ONE-LINE BIT IDENTITIES REPLACE A WHOLE LOOP?
What does n & -n evaluate to, and how does it differ from n & (n-1)?
n & -n keeps only the lowest set bit; n & (n-1) removes it. In two's complement -n = ~n + 1, which flips every bit above the lowest 1 and leaves that 1 in place, so ANDing with n isolates it (e.g. 12 & -12 = 4). n & (n-1) is the complement move — it zeroes that same bit. Isolate to read the lowest bit, strip to count or clear it.
Swap with a ^= b; b ^= a; a ^= b; starting a=5, b=9. After the first two lines, what does b hold?
b becomes 5, the old a. After a ^= b, a = 5 ^ 9. Then b ^= a is b = 9 ^ (5 ^ 9) = 5 — the two 9s cancel and old a survives. The last line a ^= b = (5^9) ^ 5 = 9 finishes the swap. Every step is XOR undoing an earlier XOR, which is exactly the x ^ y ^ y = x identity.
Reversing a 32-bit number, why must the accumulator shift left as n shifts right, for exactly 32 iterations?
You pour bits from one end into the other. res = (res << 1) | (n & 1); n >>= 1; takes n's current lowest bit and stacks it as res's newest low bit while old bits shift up. After all 32 positions, the bit that was at position 0 ends at position 31 and vice-versa — a full reversal. Fewer than 32 iterations reverses only part of the word and leaves the high bits wrong.
The classic party trick, and a clean demonstration of XOR's self-inverse property. After a ^= b, a holds the combined pattern; XOR-ing b back out of it recovers the old a into b; XOR-ing that recovered value out of the combined pattern lands the old b in a. Three lines, no third variable, because every XOR is its own undo. In real code you'd just use a temporary — but the reasoning here (that x ^ y ^ y = x) is exactly what powers Single Number and Missing Number.
“Reverse the bits of a 32-bit unsigned integer.” Rearranging bits within a fixed word is a shift-and-pour loop over the 32 positions.
Pull bits off the low end of n one at a time and stack them onto the low end of a growing result, which you shift left first to make room. After 32 rounds the bit that started at position 0 sits at position 31 and vice-versa.
// Pour n's bits, low end first, onto the result's low end. uint32_t reverseBits(uint32_t n) { uint32_t result = 0; for (int i = 0; i < 32; i++) { result = (result << 1) | (n & 1); // append lowest bit of n n >>= 1; // and drop it } return result; }
// Pour n's bits, low end first, onto the result's low end. public int reverseBits(int n) { int result = 0; for (int i = 0; i < 32; i++) { result = (result << 1) | (n & 1); // append lowest bit of n n >>>= 1; // >>> not >>: no sign extension } return result; }
# Pour n's bits, low end first, onto the result's low end. def reverseBits(n): result = 0 for _ in range(32): result = (result << 1) | (n & 1) # append lowest bit of n n >>= 1 # and drop it return result
Using a signed type or stopping early. Do the whole thing in an unsigned 32-bit type — a signed right shift of a negative number sign-extends and corrupts the result. And it must be exactly 32 iterations: fewer reverses only part of the word and leaves the high bits wrong.
Minimum Bit Flips is a two-line problem once you see it: the number of positions you must flip to turn a into b is exactly the number of positions where they differ — and a ^ b has a 1 in precisely those positions. So the answer is the set-bit count of a ^ b. XOR finds the differences; popcount (Kernighan from Unit 1) counts them.
HOW MANY BIT FLIPS TURN a INTO b?
Why is the minimum number of bit flips from a to b equal to the set-bit count of a ^ b?
Differences need one flip each, and XOR marks the differences. A position where a and b already agree needs no flip; a position where they differ needs exactly one. a ^ b puts a 1 in every differing position and 0 elsewhere, so its set-bit count is the total flips — this is the Hamming distance. It's the cleanest compose in the deck: Unit 5's XOR to find the differences, Unit 1's popcount to count them.
a = 10 (1010), b = 7 (0111). How many flips?
3. 1010 ^ 0111 = 1101. Positions 0, 2 and 3 differ (reading right to left), position 1 agrees — three 1s, so three flips. Counting them with n & (n-1) loops three times: 1101 → 1100 → 1000 → 0. XOR then popcount, and you're done.
A bit has to change exactly where a and b disagree — and that is the definition of XOR, so a ^ b marks every flip needed in one step. What is left is counting the ones, and x &= x-1 clears the lowest set bit each time, so the loop runs once per set bit rather than once per bit of width.
“Minimum flips to convert start into goal.” “Positions that differ” is XOR; “how many” is a set-bit count — popcount(a ^ b).
A flip is needed at exactly the positions where the two numbers disagree. start ^ goal has a 1 in each such position, so the answer is simply the number of set bits in that XOR — the Hamming distance.
// Flips needed = set bits of the XOR (Hamming distance). int minBitFlips(int start, int goal) { int diff = start ^ goal, count = 0; while (diff) { diff &= diff - 1; // strip a differing bit count++; } return count; }
// Flips needed = set bits of the XOR (Hamming distance). public int minBitFlips(int start, int goal) { int diff = start ^ goal, count = 0; while (diff != 0) { diff &= diff - 1; // strip a differing bit count++; } return count; }
# Flips needed = set bits of the XOR (Hamming distance). def minBitFlips(start, goal): diff, count = start ^ goal, 0 while diff: diff &= diff - 1 # strip a differing bit count += 1 return count
Comparing digit by digit, or forgetting the XOR reveals the differences for free. There's no need to loop over bit positions manually and compare — start ^ goal already isolates the differing bits, and Kernighan counts them in one pass. In Python, bin(start ^ goal).count('1') is the whole solution.
The power set — every subset of n items — has 2ⁿ members, and an n-bit number is a subset: bit i on means item i is in. So looping a plain integer mask from 0 to 2ⁿ - 1 and reading its bits generates all subsets with no recursion — the outer loop picks the subset, the inner loop reads which items it contains. It's the bitmask version of the pick/not-pick recursion tree.
HOW DO YOU LIST ALL 2ⁿ SUBSETS WITH JUST TWO LOOPS?
Why does the loop run from 0 to (1 << n) - 1, and how does a mask value encode a subset?
1<<n = 2ⁿ, and each integer is a membership vector. There are 2ⁿ subsets and 2ⁿ distinct n-bit numbers, so they correspond one-to-one. Reading bit i of the mask (mask & (1<<i)) tells you whether item i is in that subset. Iterating the masks therefore iterates the subsets — the empty set is 0, the full set is all-ones.
Items are [a, b, c] (index 0,1,2). Which subset does mask 5 = 101 represent?
{a, c}. 5 = 101 has bit 0 and bit 2 set, bit 1 clear. Bit 0 → item a in, bit 1 → item b out, bit 2 → item c in. Reading right-to-left keeps index i aligned with 1<<i. The visualiser lights exactly the chosen cells as the mask counts up.
An n-bit number is a subset: bit i on means item i is chosen. So counting a plain integer mask from 0 to 2ⁿ - 1 and reading its bits enumerates every subset — no recursion, no backtracking, just a loop inside a loop. 000 is the empty set, 111 is everything, and the 2ⁿ values in between are each a distinct combination. It is the cleanest thing bit manipulation buys you: a power set as a for-loop.
0..2ⁿ-1 is one subset — no recursion at all.
“Return all subsets of the array” with n small (≤ ~20). List-all over a small n is the bitmask enumeration signature.
Each subset corresponds to an n-bit mask: bit i set means nums[i] is included. Loop mask from 0 to 2ⁿ - 1; for each, read its bits to build one subset. No recursion, no backtracking — the integer is the choice vector.
// Each mask 0..2^n-1 IS a subset; read its bits. vector<vector<int>> subsets(vector<int>& nums) { int n = nums.size(); vector<vector<int>> res; for (int mask = 0; mask < (1 << n); mask++) { vector<int> subset; for (int i = 0; i < n; i++) if (mask & (1 << i)) // is item i chosen? subset.push_back(nums[i]); res.push_back(subset); } return res; }
// Each mask 0..2^n-1 IS a subset; read its bits. public List<List<Integer>> subsets(int[] nums) { int n = nums.length; List<List<Integer>> res = new ArrayList<>(); for (int mask = 0; mask < (1 << n); mask++) { List<Integer> subset = new ArrayList<>(); for (int i = 0; i < n; i++) if ((mask & (1 << i)) != 0) // is item i chosen? subset.add(nums[i]); res.add(subset); } return res; // no recursion anywhere }
# Each mask 0..2^n-1 IS a subset; read its bits. def subsets(nums): n = len(nums) res = [] for mask in range(1 << n): subset = [nums[i] for i in range(n) if mask & (1 << i)] res.append(subset) return res
Looping the mask only to n instead of 2ⁿ. The outer bound is 1 << n (the number of subsets), not n. Also keep index i aligned with 1<<i when reading bits, and note this only scales while n is small — 2ⁿ explodes past ~20.
The whole XOR family rests on one fact from the warmup: a ^ a = 0 and a ^ 0 = a, and XOR is order-independent. So XOR-ing an array where every value appears twice except one makes all the pairs annihilate, leaving the lone element — O(n) time, O(1) space, no hash set. Missing Number is the same idea: XOR all the indices 0..n together with all the values, and every present number cancels its index, leaving the one that's absent.
WHEN EVERYTHING PAIRS UP EXCEPT ONE, HOW DO YOU FIND THE ODD ONE OUT?
Single Number XORs the whole array. Why does the answer fall out, and why is order irrelevant?
Commutativity + self-cancellation. Because x ^ y = y ^ x and x ^ x = 0, you can imagine reordering the array so each duplicate sits next to its twin — every pair becomes 0, and 0 XORed with the lone value leaves that value. No sorting or reordering actually happens; the algebra guarantees it regardless of input order. That's why it's O(1) space where a hash set is O(n).
Array [4, 1, 2, 1, 2]. What does XOR-ing all five give?
4. 4 ^ 1 ^ 2 ^ 1 ^ 2: the pair of 1s gives 0, the pair of 2s gives 0, leaving 4 ^ 0 ^ 0 = 4. The mechanism slide shows the running value collapsing to 0 each time a pair completes, then holding the survivor. This exact array is what the xor visualiser runs.
Missing Number: an array holds n distinct values from 0..n with one absent. How does XOR find the missing one?
XOR the indices and the values into one accumulator. Fold 0 ^ 1 ^ … ^ n together with arr[0] ^ arr[1] ^ …. Every number that is present appears once as a value and once as an index, so it cancels; the number that's missing appears only as an index and survives. It's the same a^a=0 trick with the array's own positions supplying the partners. (Summing with n(n+1)/2 also works but can overflow.)
One identity carries the entire family: a ^ a = 0 and a ^ 0 = a. XOR is associative and commutative, so XOR-ing the whole array lets every duplicated value cancel with its partner regardless of order, and whatever appears an odd number of times is left standing. No hash set, no sorting, O(1) space. Watch the running value collapse to 0 each time a pair completes — the survivor is the answer, and every Single-Number variant is a twist on this cancellation.
“Every element appears twice except one; find it, in O(1) space.” The O(1)-space + “pairs except one” combo is the XOR sweep.
XOR all the numbers together. Because a ^ a = 0 and XOR is order-independent, every duplicated pair cancels to zero and the single element — which has no partner — is left in the accumulator.
// XOR everything; duplicates cancel, the single survives. int singleNumber(vector<int>& nums) { int x = 0; for (int v : nums) x ^= v; // a ^ a = 0 return x; }
// XOR everything; duplicates cancel, the single survives. public int singleNumber(int[] nums) { int x = 0; for (int v : nums) x ^= v; // a ^ a = 0 return x; }
# XOR everything; duplicates cancel, the single survives. def singleNumber(nums): x = 0 for v in nums: x ^= v # a ^ a = 0 return x
Reaching for a hash set or sort when XOR is free. Those work but cost O(n) space or O(n log n) time; XOR is one pass and one integer. The catch is that it only works when every other element appears an even number of times — if the promise is “thrice except one” (Single Number II), XOR breaks and you need bit counting mod 3.
“n distinct numbers from 0..n, one missing.” A complete range with a single gap is a XOR (or sum) of index against value.
XOR every index 0..n together with every array value into one accumulator. Each number that's present appears once as a value and once as an index, so it cancels; the missing number appears only as an index and survives. Overflow-free, unlike the sum formula.
// XOR indices against values; the missing index survives. int missingNumber(vector<int>& nums) { int x = nums.size(); // the index n itself for (int i = 0; i < (int)nums.size(); i++) x ^= i ^ nums[i]; // each present value cancels its index return x; }
// XOR indices against values; the missing index survives. public int missingNumber(int[] nums) { int x = nums.length; // the index n itself for (int i = 0; i < nums.length; i++) x ^= i ^ nums[i]; // each present value cancels its index return x; // cannot overflow, unlike the sum trick }
# XOR indices against values; the missing index survives. def missingNumber(nums): x = len(nums) # the index n itself for i, v in enumerate(nums): x ^= i ^ v # each present value cancels its index return x
The sum formula overflows; the index range is off by one. n(n+1)/2 - sum works but can overflow for large n — XOR never does. And the range is 0..n for an array of length n, so seed the accumulator with n (or XOR i up to and including n) or you'll miss the top index.
Single Number II breaks the plain-XOR trick: here every element appears three times except one, and a ^ a ^ a = a, so pairs no longer vanish. The fix generalises the idea to counting each bit position mod 3. For each of the 32 bit columns, add up how many array numbers have that bit set; the triples contribute a multiple of 3, so count % 3 leaves exactly the answer's bit. Rebuild the answer column by column. (The slick ones/twos bitmask automaton does the same in O(1) space.)
WHEN EVERY ELEMENT APPEARS THREE TIMES EXCEPT ONE, WHY DOES XOR FAIL — AND WHAT REPLACES IT?
Why does the Single Number I trick (XOR everything) fail when each element appears three times instead of twice?
XOR annihilates in pairs, not triples. a ^ a = 0 handles even multiplicities; with an odd count like 3, one copy survives each triple, so XOR-ing everything leaves a jumble of all the tripled values plus the unique one — not the answer. You need a counter that resets every three, which is what per-bit count % 3 (or the ones/twos automaton) provides.
In the bit-count-mod-3 method, how do you recover the unique element's value?
Tally each column mod 3, then reassemble. Each number that appears three times contributes 0 or 3 to a given bit column, i.e. a multiple of 3; only the unique element contributes an extra 0 or 1. So count % 3 at position i is exactly the unique element's bit i. Set that bit in the result (if (count % 3) ans |= (1 << i)) across all 32 columns and you've rebuilt the answer — O(32n) time, O(1) space.
The single-number trick fails here: three copies XOR to a, not to 0. So the array is read as columns of bits instead. A value appearing three times contributes 3 to every column it touches, which vanishes mod 3 — so taking each column mod 3 leaves exactly the loner's bits standing, and nothing else can survive.
“Every element appears three times except one.” The “thrice except one” wording is the tell that plain XOR won't do — count bits mod 3.
XOR cancels pairs, not triples, so generalise: for each of the 32 bit positions, count how many array numbers have that bit set. Tripled elements contribute a multiple of 3 to each column, so count % 3 leaves exactly the unique element's bit there. Reassemble the answer column by column.
// Each bit column mod 3 leaves the unique element's bit. int singleNumber(vector<int>& nums) { int ans = 0; for (int i = 0; i < 32; i++) { int count = 0; for (int v : nums) if (v & (1 << i)) count++; // tally this column if (count % 3) ans |= (1 << i); // the odd-one-out's bit } return ans; }
// Each bit column mod 3 leaves the unique element's bit. public int singleNumber(int[] nums) { int ans = 0; for (int i = 0; i < 32; i++) { int count = 0; for (int v : nums) if ((v & (1 << i)) != 0) count++; // tally this column if (count % 3 != 0) ans |= (1 << i); // the odd-one-out's bit } return ans; }
# Each bit column mod 3 leaves the unique element's bit. def singleNumber(nums): ans = 0 for i in range(32): count = sum((v >> i) & 1 for v in nums) # tally this column if count % 3: ans |= (1 << i) # the odd-one-out's bit # handle Python's unbounded ints for negatives if needed return ans
Assuming XOR still works, or mishandling negatives. Plain XOR fails because a ^ a ^ a = a. The bit-count method is robust, but in Python integers are unbounded, so a negative answer needs a two's-complement fixup after bit 31. The ones/twos automaton (ones = (ones ^ v) & ~twos; twos = (twos ^ v) & ~ones) does the same job in true O(1) space.
Single Number III has two loners (each once) among pairs. XOR-ing everything gives a ^ b — not a single answer, but a fingerprint of where a and b differ. Pick any set bit of a ^ b (the lowest, xr & -xr, is easiest): a and b differ there, so it splits the array into two groups — one where that bit is on, one where it's off. Each loner lands in a different group, every pair stays together, so XOR-ing each group gives one answer apiece. One XOR becomes two.
WITH TWO ELEMENTS APPEARING ONCE, HOW DO YOU SPLIT ONE XOR INTO TWO?
After XOR-ing the whole array you have xr = a ^ b. Why does any set bit of xr cleanly separate a from b?
A differing bit separates them by construction. a ^ b is 1 only where the two answers disagree, so at such a position one answer has a 1 and the other a 0 — they must fall into different groups when you partition on that bit. Duplicated values are identical, so both copies share the bit and stay together, cancelling within their group. XOR each group and you get a from one and b from the other.
If xr = a ^ b = 6 (110), which bit does xr & -xr pick to split on?
Bit 1, the mask 2. 6 = 110; its lowest set bit is position 1. xr & -xr isolates it (110 & 010 = 010). Any set bit of xr would work to split on — the lowest is just the cheapest to grab. You then bucket each number by num & mask and XOR the two buckets separately.
XOR-ing everything gives a ^ b, which is not an answer. But any set bit of it is a position where the two loners differ, so partitioning on that bit puts one loner in each group — and every duplicate lands in the same group as its partner, so it still cancels. Two ordinary single-number problems, solved at once.
“Exactly two elements appear once; everything else twice.” Two loners with O(1) space is XOR-then-split.
XOR the whole array to get xr = a ^ b. Isolate any set bit of it with xr & -xr — a and b differ there. Partition the array on that bit and XOR each half separately: pairs cancel within their half, and the two loners land in different halves, giving a and b.
// XOR all, split on a differing bit, XOR each half. vector<int> singleNumber(vector<int>& nums) { long xr = 0; for (int v : nums) xr ^= v; // xr = a ^ b int mask = xr & (-xr); // lowest differing bit int a = 0, b = 0; for (int v : nums) { if (v & mask) a ^= v; // bit set -> group A else b ^= v; // bit clear -> group B } return {a, b}; }
// XOR all, split on a differing bit, XOR each half. public int[] singleNumber(int[] nums) { int xr = 0; for (int v : nums) xr ^= v; // xr = a ^ b int mask = xr & (-xr); // lowest differing bit int a = 0, b = 0; for (int v : nums) { if ((v & mask) != 0) a ^= v; // bit set -> group A else b ^= v; // bit clear -> group B } return new int[]{a, b}; // each pair stayed together }
# XOR all, split on a differing bit, XOR each half. def singleNumber(nums): xr = 0 for v in nums: xr ^= v # xr = a ^ b mask = xr & (-xr) # lowest differing bit a = b = 0 for v in nums: if v & mask: a ^= v # bit set -> group A else: b ^= v # bit clear -> group B return [a, b]
Splitting on a bit that isn't set in xr. The split bit must be one where a and b differ — i.e. a set bit of a ^ b. xr & -xr guarantees that. Using an arbitrary bit can put both loners in the same bucket and the method collapses. Use a wider type for xr to dodge the -INT_MIN corner.
XOR of a contiguous range is a closed-form trick, not a loop. XOR-ing 1 ^ 2 ^ … ^ n follows a period-4 pattern in n: if n % 4 == 0 the result is n; == 1 gives 1; == 2 gives n + 1; == 3 gives 0. For an arbitrary range [a, b], use the prefix identity XOR(a..b) = XOR(1..b) ^ XOR(1..a-1) — the same trick as prefix sums, because XOR is its own inverse. It's a concept unit: no LeetCode row, but the identity shows up inside harder problems.
WHAT IS 1 ^ 2 ^ … ^ n IN CONSTANT TIME?
XOR(1..n) has a period-4 closed form. What is it when n % 4 == 0?
When n % 4 == 0, XOR(1..n) = n. The full table is {0: n, 1: 1, 2: n+1, 3: 0}. It arises because consecutive groups of four (4k, 4k+1, 4k+2, 4k+3) XOR to 0, so only the tail position matters. Memorise the four cases and any prefix XOR is a constant-time lookup — no loop over the range.
Using the pattern, what is 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6?
7. n = 6, 6 % 4 == 2, so XOR(1..6) = n + 1 = 7. Check by hand: 1^2=3, ^3=0, ^4=4, ^5=1, ^6=7. For a sub-range like 3..6 you'd compute XOR(1..6) ^ XOR(1..2) = 7 ^ 3 = 4, again with no loop.
The running prefix does not wander: it takes only four shapes, decided by n mod 4. Watch it repeat as n passes 4 and 8. Once that is visible the O(n) loop is unnecessary and any range is prefix(r) ^ prefix(l-1), because the shared part cancels itself.
Maximum XOR of two numbers is where bits meet the trie (a taste of a later sheet topic). Brute force is O(n²); the trick is to store every number's 32-bit representation in a binary trie (each node has a 0-child and a 1-child), then for each number walk the trie from the most significant bit, greedily taking the opposite bit whenever it exists. Choosing the opposite bit forces a 1 into that position of the XOR — and because you go MSB-first, maximising a higher bit always beats anything below it. This unit has no lecture in the playlist; the drills carry it.
HOW DO YOU FIND THE MAX-XOR PAIR WITHOUT CHECKING ALL n² PAIRS?
Walking the trie to maximise XOR with a query number, why do you prefer the opposite bit at each step?
Opposite bits differ, and differing bits contribute 1 to the XOR. You want as many high 1-bits in the result as possible. At each level you ask the trie: “is there a stored number whose bit here is the opposite of mine?” If yes, take it — that guarantees a 1 in this position. Falling back to the same bit (a 0 in the XOR) only happens when no opposite branch exists.
Why must the greedy walk start from the most significant bit rather than the least?
High bits dominate the value. Because 2ᵏ is larger than every lower bit put together, a 1 at position k is worth more than any pattern below it. Greedy only works if you lock in the most valuable bit first, so you descend MSB→LSB, taking the opposite branch when available. Reversing the order could trade a high 1 for several low ones — a strictly worse result.
A trie over the bits, walked from the top. At each level the greedy move is the branch that disagrees with the query, because a 1 at a high position outweighs every bit below it combined — so greed is safe here in a way it usually is not. Where the preferred branch is missing there is no choice to make, and that bit of the answer is simply 0.
“Maximum XOR over all pairs.” Maximising XOR bit by bit, over a whole array, is the binary-trie greedy — the O(n²) brute force is the tell you need it.
Insert every number's 32 bits (MSB first) into a binary trie. Then for each number, walk the trie from the top bit, at each level taking the opposite branch when it exists (forcing a 1 into the XOR at that high position) and falling back to the same branch otherwise. Track the best XOR seen.
// Binary trie; greedily take the opposite bit, MSB first. struct Node { Node* ch[2] = {nullptr, nullptr}; }; int findMaximumXOR(vector<int>& nums) { Node* root = new Node(); for (int x : nums) { // insert every number Node* cur = root; for (int b = 31; b >= 0; b--) { int bit = (x >> b) & 1; if (!cur->ch[bit]) cur->ch[bit] = new Node(); cur = cur->ch[bit]; } } int best = 0; for (int x : nums) { // query every number Node* cur = root; int cur_xor = 0; for (int b = 31; b >= 0; b--) { int bit = (x >> b) & 1; if (cur->ch[1 - bit]) { // opposite exists -> a 1 here cur_xor |= (1 << b); cur = cur->ch[1 - bit]; } else cur = cur->ch[bit]; } best = max(best, cur_xor); } return best; }
// Binary trie; greedily take the opposite bit, MSB first. static class Node { Node[] ch = new Node[2]; } public int findMaximumXOR(int[] nums) { Node root = new Node(); for (int x : nums) { // insert every number Node cur = root; for (int b = 31; b >= 0; b--) { int bit = (x >> b) & 1; if (cur.ch[bit] == null) cur.ch[bit] = new Node(); cur = cur.ch[bit]; } } int best = 0; for (int x : nums) { // then query with each Node cur = root; int val = 0; for (int b = 31; b >= 0; b--) { int bit = (x >> b) & 1, want = bit ^ 1; // prefer to DIFFER if (cur.ch[want] != null) { val |= (1 << b); cur = cur.ch[want]; } else cur = cur.ch[bit]; } best = Math.max(best, val); } return best; // MSB-first: a high bit outweighs all below }
# Binary trie; greedily take the opposite bit, MSB first. def findMaximumXOR(nums): root = {} for x in nums: # insert every number cur = root for b in range(31, -1, -1): bit = (x >> b) & 1 cur = cur.setdefault(bit, {}) best = 0 for x in nums: # query every number cur, cur_xor = root, 0 for b in range(31, -1, -1): bit = (x >> b) & 1 if (1 - bit) in cur: # opposite exists -> a 1 here cur_xor |= (1 << b) cur = cur[1 - bit] else: cur = cur[bit] best = max(best, cur_xor) return best
Walking LSB-first, or not padding to a fixed width. You must go from the most significant bit so a high 1 is secured before any low bits are considered — greedy is only correct top-down. Insert every number to the same fixed width (e.g. 32 bits) so paths line up; a bit-length hash approach exists too, but the trie is the clean mental model.
Arithmetic is just shifts and logic underneath. This lecture rebuilds division without /: to compute a / b, repeatedly double the divisor (b, 2b, 4b, …) while it still fits in the remaining dividend, subtract the largest such multiple, and accumulate the corresponding power of two into the quotient — long division in binary. The same shift-and-logic mindset gives addition without + (sum is XOR, carry is AND shifted left) and the AND of a whole range (the common high prefix). Mind the sign handling and the INT_MIN overflow.
HOW DO YOU DIVIDE, ADD, OR AND-A-RANGE USING ONLY SHIFTS AND LOGIC?
In division-by-shifts, why double the divisor (b, 2b, 4b, …) instead of subtracting b one at a time?
Doubling turns a linear count into a logarithmic one. Naively subtracting the divisor until you can't is O(a/b) — up to ~2³¹ iterations. Instead, find the biggest shifted divisor b << k that still fits, subtract it, add 1 << k to the quotient, and repeat on the remainder. Each step nails one quotient bit from the top down — that's binary long division, O(log²n).
Which single input pair is the notorious overflow case for integer division, and how do you handle it?
INT_MIN / -1. The mathematical result is +2³¹, one past INT_MAX, so it overflows a signed 32-bit result. Detect it up front and return INT_MAX per the problem's convention. Doing the accumulation in long long and separating the sign avoids intermediate overflow everywhere else.
Addition with no + anywhere. a ^ b is the sum of every column that does not carry, and (a & b) << 1 is precisely the carries, shifted one place left because that is where a carry belongs. Feeding them back can create new carries, so the two steps repeat until the carry is 0 — it is the schoolbook method with the loop made explicit.
“Divide without *, / or %.” That prohibition points straight at shift-and-subtract (binary long division).
Work with absolute values in a 64-bit type. Repeatedly find the largest divisor << k that still fits in the remaining dividend, subtract it, and add 1 << k to the quotient. Apply the sign at the end and clamp the INT_MIN / -1 overflow.
// Binary long division: double the divisor, subtract, accumulate. int divide(int dividend, int divisor) { if (dividend == INT_MIN && divisor == -1) return INT_MAX; // overflow long a = labs(dividend), b = labs(divisor), quotient = 0; bool neg = (dividend < 0) ^ (divisor < 0); while (a >= b) { long temp = b, mult = 1; while ((temp << 1) <= a) { temp <<= 1; mult <<= 1; } // largest fit a -= temp; quotient += mult; } return neg ? -quotient : quotient; }
// Binary long division: double the divisor, subtract, accumulate. public int divide(int dividend, int divisor) { if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE; // +2^31 does not fit long a = Math.abs((long) dividend), b = Math.abs((long) divisor), quotient = 0; boolean neg = (dividend < 0) ^ (divisor < 0); while (a >= b) { long temp = b, mult = 1; while (a >= (temp << 1)) { temp <<= 1; mult <<= 1; } // largest 2^k*b a -= temp; quotient += mult; } return (int) (neg ? -quotient : quotient); }
# Binary long division: double the divisor, subtract, accumulate. def divide(dividend, divisor): INT_MAX, INT_MIN = 2**31 - 1, -2**31 if dividend == INT_MIN and divisor == -1: return INT_MAX # overflow a, b, quotient = abs(dividend), abs(divisor), 0 neg = (dividend < 0) ^ (divisor < 0) while a >= b: temp, mult = b, 1 while (temp << 1) <= a: temp <<= 1; mult <<= 1 # largest fit a -= temp quotient += mult return -quotient if neg else quotient
The INT_MIN / -1 overflow, and repeated single subtraction. Subtracting the divisor one at a time is O(dividend) and times out; you must double it. And INT_MIN / -1 = +2³¹ doesn't fit — special-case it to INT_MAX and do the arithmetic in a 64-bit type so the doublings never overflow.
“Sum of two integers without + or -.” Addition from logic gates is XOR for the sum, AND-shifted for the carry.
Add binary the way hardware does: the sum-without-carry of two bits is their XOR, and the carry is their AND shifted left one. Loop — new a is the XOR, new b is the shifted carry — until the carry is zero.
// sum = XOR, carry = AND << 1, repeat until no carry. int getSum(int a, int b) { while (b != 0) { unsigned carry = (unsigned)(a & b) << 1; // carry bits, shifted a = a ^ b; // sum without carry b = carry; // propagate } return a; }
// sum = XOR, carry = AND << 1, repeat until no carry. public int getSum(int a, int b) { while (b != 0) { int carry = (a & b) << 1; // carry bits, shifted a = a ^ b; // sum without carry b = carry; // propagate } return a; }
# sum = XOR, carry = AND << 1, repeat until no carry. def getSum(a, b): mask = 0xFFFFFFFF while b & mask: carry = (a & b) << 1 # carry bits, shifted a = a ^ b # sum without carry b = carry a &= mask return a if a <= 0x7FFFFFFF else ~(a ^ mask) # handle negatives
Signed-overflow on the carry, and Python's unbounded ints. In C++ shift the carry as unsigned to avoid UB. In Python integers never overflow, so the carry loop won't terminate for negative results — mask to 32 bits each round and convert back with two's complement at the end.
“Bitwise AND of every number in [left, right].” AND over a contiguous range collapses to the numbers' common binary prefix.
Any bit that changes anywhere in the range becomes 0 in the AND (some number has it off). Only the high bits that left and right share stay 1. So shift both right until they're equal (that's the common prefix), then shift the shared value back left by the same amount.
// The AND of a range is the common high prefix of the ends. int rangeBitwiseAnd(int left, int right) { int shift = 0; while (left != right) { // strip differing low bits left >>= 1; right >>= 1; shift++; } return left << shift; // pad the low bits back as zeros }
// The AND of a range is the common high prefix of the ends. public int rangeBitwiseAnd(int left, int right) { int shift = 0; while (left != right) { // strip differing low bits left >>= 1; right >>= 1; shift++; } return left << shift; // pad the low bits back as zeros }
# The AND of a range is the common high prefix of the ends. def rangeBitwiseAnd(left, right): shift = 0 while left != right: # strip differing low bits left >>= 1 right >>= 1 shift += 1 return left << shift # pad the low bits back as zeros
ANDing every number in the range. For a wide range that's billions of operations. The insight is that any low bit which flips even once across the range is 0 in the result, so only the shared high prefix of left and right survives — an O(log n) shift, not an O(range) loop. (Equivalently, while (right > left) right &= right - 1;.)
Two number-theory staples that sit beside bit manipulation on the sheet, neither with a lecture here. Count Primes uses the Sieve of Eratosthenes: mark every composite by walking multiples of each prime, starting at i·i (smaller multiples were already marked by smaller primes) — O(n log log n). Pow(x, n) uses fast exponentiation: xⁿ = (x^(n/2))², halving the exponent each step for O(log n) — the same halving idea as binary representation, which is why it lives near bits.
HOW DO YOU SIEVE PRIMES, AND POWER A NUMBER, IN LOG-ISH TIME?
In the Sieve of Eratosthenes, why can the inner marking loop start at i·i rather than 2·i?
Smaller multiples were already crossed off. A multiple k·i with k < i also equals i·k, and k has a prime factor ≤ k < i that sieved it earlier. So the first new composite that prime i is responsible for is i·i. Starting there is the standard optimisation and changes nothing about correctness.
Fast exponentiation computes 3⁵. Using xⁿ = (x^(n/2))² (times an extra x when n is odd), how many multiplications, roughly?
~O(log n) multiplications. 3⁵ = 3⁴ · 3 = (3²)² · 3 = 81 · 3 = 243. You square to climb powers of two (3→9→81) and multiply in an extra x for each set bit of the exponent — five in binary is 101, so two squarings and two multiplies. Naive repeated multiplication is O(n); this is O(log n). Remember to handle negative n by inverting x and guarding INT_MIN.
Filed under maths, but it is a bit problem: 313 where 13 is 01101. The squarings form a ladder computed regardless — each is the previous one squared — and the set bits decide which rungs get multiplied in. Bit 1 is 0, so that squaring is skipped entirely. That is why the cost is log(e) and not e.
“How many primes below n?” Counting primes up to a bound is the Sieve of Eratosthenes.
Assume every number is prime, then cross out the multiples of each prime you meet. For prime i, start marking at i·i (smaller multiples already have a smaller prime factor) and step by i. Whatever's still unmarked below n is prime.
// Sieve of Eratosthenes: cross out multiples from i*i. int countPrimes(int n) { if (n < 3) return 0; vector<bool> isPrime(n, true); isPrime[0] = isPrime[1] = false; for (int i = 2; (long)i * i < n; i++) if (isPrime[i]) for (int j = i * i; j < n; j += i) // start at i*i isPrime[j] = false; int count = 0; for (int i = 2; i < n; i++) if (isPrime[i]) count++; return count; }
// Sieve of Eratosthenes: cross out multiples from i*i. public int countPrimes(int n) { if (n < 3) return 0; boolean[] isPrime = new boolean[n]; Arrays.fill(isPrime, true); isPrime[0] = isPrime[1] = false; for (int i = 2; (long) i * i < n; i++) if (isPrime[i]) for (int j = i * i; j < n; j += i) // start at i*i, not 2*i isPrime[j] = false; int count = 0; for (boolean p : isPrime) if (p) count++; return count; }
# Sieve of Eratosthenes: cross out multiples from i*i. def countPrimes(n): if n < 3: return 0 is_prime = [True] * n is_prime[0] = is_prime[1] = False i = 2 while i * i < n: if is_prime[i]: for j in range(i * i, n, i): # start at i*i is_prime[j] = False i += 1 return sum(is_prime)
Trial-dividing each number, or starting the inner loop at 2i. Checking primality one number at a time is O(n√n) and too slow; the sieve shares work across all numbers. Starting the marking at i·i (not 2i) skips composites already crossed off, and watch the bound: it's primes below n, so index up to n-1.
n is the iterative form.
“Compute xⁿ efficiently.” A power with a large exponent is fast exponentiation (binary / square-and-multiply).
Halve the exponent each step: xⁿ = (x^(n/2))², and multiply in an extra x when n is odd. Iteratively, square x as you shift n right, folding x into the answer whenever the current low bit of n is 1. Handle negative n by inverting.
// Square-and-multiply: fold x in on each set bit of n. double myPow(double x, int n) { long N = n; // widen to avoid INT_MIN overflow if (N < 0) { x = 1 / x; N = -N; } double result = 1.0; while (N > 0) { if (N & 1) result *= x; // this bit of the exponent is 1 x *= x; // square the base N >>= 1; // next bit } return result; }
// Square-and-multiply: fold x in on each set bit of n. public double myPow(double x, int n) { long N = n; // widen to avoid MIN_VALUE overflow if (N < 0) { x = 1 / x; N = -N; } double result = 1.0; while (N > 0) { if ((N & 1) == 1) result *= x; // this bit of the exponent is 1 x *= x; // square for the next bit up N >>= 1; } return result; }
# Square-and-multiply: fold x in on each set bit of n. def myPow(x, n): if n < 0: x, n = 1 / x, -n result = 1.0 while n > 0: if n & 1: result *= x # this bit of the exponent is 1 x *= x # square the base n >>= 1 # next bit return result
Naive O(n) looping, and the INT_MIN negation. Multiplying x by itself n times is far too slow for large n and can TLE. Squaring halves the exponent each step. And -INT_MIN overflows a 32-bit int, so widen n to a 64-bit type before negating.
You are told an array has every number twice except two that appear once. Plain XOR of everything gives you a ^ b — now what?
Split on a differing bit. a ^ b has a 1 exactly where a and b differ, so any set bit of it partitions the numbers into “bit on” and “bit off”. a and b land in different buckets, every duplicate lands with its twin, so XOR-ing each bucket leaves one answer apiece. mask = xr & -xr isolates the lowest set bit. That is Single Number III — the whole trick is turning one XOR into two.
Why does n & (n - 1) clear exactly the lowest set bit, and nothing else?
The borrow stops at the lowest 1. In n - 1 the borrow ripples up through the trailing zeros (turning them to 1s) until it hits the lowest set bit, which becomes 0. Every bit above that is untouched. ANDing n with n-1 therefore agrees on all the high bits and kills exactly the lowest 1 — so looping it counts set bits (Kernighan) and testing (n & (n-1)) == 0 detects a single-bit number (power of two).
Bit bugs compile and return believable numbers: a missing positivity guard, a precedence slip, an XOR sweep on the wrong kind of data, a shift into the sign bit. Every one passes the small test.
1 << 31 overflows a signed 32-bit int (undefined behaviour in C++); use 1u << 31 or a long long. Shifting by 32 or more is also UB. Reverse Bits and any full-word mask hit this — it passes small tests and detonates on the high bit.
(n & (n-1)) == 0 is also true for n == 0, which is not a power of two. And for negatives in two's complement it misbehaves. The correct test is n > 0 && (n & (n-1)) == 0.
n & 1 == 0 parses as n & (1 == 0) = n & 0 = 0, always false. Bitwise operators sit below comparison in C/C++/Java precedence — parenthesise: (n & 1) == 0. This one compiles and quietly returns the wrong answer every time.
The a^a=0 trick only isolates the answer when every other element appears an even number of times. Single Number II (each thrice) breaks it — XOR leaves garbage; you need per-bit counting mod 3 instead. Check the multiplicity the problem promises before reaching for XOR.
INT_MIN / -1 is +2³¹, which doesn't fit in an int — the one case shift-and-subtract division must special-case and clamp to INT_MAX. Do the work in long long and handle signs separately to avoid it.
n | mask sets a bit to 1 idempotently; n ^ mask flips it, so applying it twice is a no-op and applying it to an already-set bit clears it. Reaching for XOR when you wanted OR is a classic silent bug — set is |, toggle is ^.
Twelve techniques, one page. The right-hand column is the phrase in the statement that should make each line come to mind — the night-before surface.
Read, set, clear, toggle; count with n & (n-1); enumerate subsets with a mask; and lean on a ^ a = 0 for the whole Single-Number family. Every operator ran live on the 32-cell strip, and every concept was primed, watched, drilled and applied. Next on the sheet: recursion & dynamic programming, where the bitmask returns as state.
All 9 playlist lectures are used. XOR-of-a-range (L8) is a concept unit — no judge link was supplied. Maximum XOR (a bit-trie) and the Advanced-Maths pair (Count Primes, Pow) go beyond the sheet at the reader's request and carry no lecture.
Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.
Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.