Choose the algebra from what may disappear

An array has pairs and one singleton. A frequency map works.

Decision: Which fixed-size summary can erase pairs in any order? Does the same summary erase triples?

1 / 9

Add Binary — predict before coding

A carry is the complete information one bit position needs from lower positions. Working from the right avoids converting an arbitrarily long input into a fixed-width integer.

Decision: Add 10111 and 00101. After the first two low positions, emitted bits are 00 and carry is 1. Complete the next column, including its outgoing carry, then finish the result. Why would resetting carry before using it fail?

Presenter notes

Model answer: The next column totals 1+1+1=3, so emit 1 and retain carry 1. The next total is 0+0+1=1, then the final total is 1+0=1. Emitted low-to-high bits are 0,0,1,1,1, giving 11100. Resetting the incoming carry drops a contribution from the already-processed suffix and breaks the positional-addition invariant.

Correctness argument: After processing k low-order positions, the reversed output stores the correct low k bits of the sum, and carry is the quotient that must be added at the next position. Adding the two available input bits and carry produces a total from 0 to 3; remainder modulo 2 is the next result bit and quotient by 2 is the new carry. This preserves the invariant. The loop stops only after both inputs and carry are exhausted. Reversing the collected bits restores most-significant-first order without changing their values.

Debugging prompt: Test unequal lengths, a long carry chain, and all-zero strings. Do not trim leading zeroes silently: the existing implementation retains at least the maximum supplied input width.

2 / 9

Reverse Bits — predict before coding

Fixed width is the point. Reversing only the significant binary digits of 1 would return 1, but reversing all 32 positions places that bit at position 31.

Decision: A byte-oriented implementation reverses the eight bits inside each byte but leaves byte order unchanged. On uint32(1), it returns 0x00000080. What second transformation repairs full 32-bit reversal, and why?

Presenter notes

Model answer: Reverse the order of the four bytes as well, producing 0x80000000. A bit at byte position q and within-byte position r must move to byte 3-q and bit 7-r. Reversing only within bytes handles the second coordinate and misses the first; composing both transformations maps bit i to 31-i.

Correctness argument: After k iterations, the result holds the reverse of the original k least-significant bits, and the shifted input contains the remaining original bits. Shifting result left makes space for the next bit; OR with n&1 appends it. Shifting n right discards exactly the consumed bit. After 32 steps every original position has moved to its mirrored position, including leading zero positions. The uint32 types enforce logical shifts and exactly the requested width.

Debugging prompt: Test zero, all ones, every single-bit input, and alternating masks. A loop that stops when n becomes zero loses the fixed-width leading positions.

3 / 9

Number of 1 Bits — predict before coding

Subtracting one flips the lowest set bit to zero and every lower zero to one. AND with the original keeps higher bits and clears exactly that lowest set bit.

Decision: A proposed test checks HammingWeight(x)+HammingWeight(^x)==32 for uint32 inputs. A broken implementation always returns 16. Would it pass, and what independent exact cases should accompany that property?

Presenter notes

Model answer: It passes for every input because 16+16=32. Add exact expectations such as zero→0, all-one uint32→32, and a one-hot input→1. The complement identity is valid, but a property relating two outputs can be satisfied by a wrong implementation. Ground it in exact known behavior as well.

Correctness argument: For nonzero n, write its low portion as a 1 followed by k zeroes. The same portion of n-1 is a 0 followed by k ones, while higher bits are unchanged. Their AND therefore removes exactly one set bit and changes no higher set bits. Each loop iteration increments count once and reduces the number of remaining ones by one. When n reaches zero, count equals the original population count. Starting at zero performs no subtraction, avoiding any need to reason about unsigned wrap in that branch.

Debugging prompt: Test sparse inputs as well as dense masks. This loop counts set bits, not the position of the highest set bit. Keep the input unsigned and distinguish a fixed 32-bit bound from a variable-width analysis.

4 / 9

Single Number — predict before coding

XOR is a cancellation operation over each bit position. Commutativity lets equal pairs cancel even when their occurrences are far apart in the input.

Decision: Both [0,4,4] and [1,2,3] have total XOR zero. Does a zero result prove that a valid singleton zero exists? Explain what the algorithm assumes instead of checking.

Presenter notes

Model answer: No. The first input has the promised paired values and singleton zero. The second has three different singletons and violates the promise, even though 1 XOR 2 XOR 3=0. The fold computes an algebraic summary, not a validation of occurrence counts; correctness depends on the input multiplicity precondition.

Correctness argument: The running accumulator is the XOR of every processed entry. XOR is associative and commutative, x XOR x is zero, and x XOR zero is x. Therefore the final expression can be regrouped into zero-valued pairs plus the one unpaired value. This holds for signed values as bit patterns as well as positive values. The proof depends on the exact multiplicity promise; with several singleton values the result would be their XOR, not one selected singleton.

Debugging prompt: Do not deduplicate the input before the fold. Test a singleton zero, negative values, and pairs separated by other values. Missing multiplicity guarantees cannot be validated by this algorithm alone.

5 / 9

Single Number II — predict before coding

Replace pair cancellation with per-bit counting modulo three. A triplicated value contributes either zero or three to every bit count, leaving only the singleton’s bit pattern.

Decision: While reading [6,6,6,-1], after the first two entries some bit-count residues equal 2. Are those residues already the singleton’s bits? Identify when cancellation becomes a valid reconstruction argument.

Presenter notes

Model answer: No. A prefix may contain only part of a promised triple, and a residue of 2 is not a binary bit. After every input is processed, each repeated value contributes exactly three copies per set bit, leaving residues 0 or 1 from the singleton. Reconstruct the complete signed-32-bit pattern only at that point; for this input it represents -1.

Correctness argument: For each of 32 bit positions, sum that position over the int32 representations of all inputs. Every repeated value contributes a multiple of three, so the remainder is exactly the singleton bit. Setting positions with nonzero remainder reconstructs its full 32-bit pattern. Building the result as int32 is necessary for a set sign bit to represent a negative value; converting that signed result back to int preserves the intended signed value. The existing int32 conversion makes this a 32-bit algorithm, not a full-width int algorithm on every architecture.

Debugging prompt: Test the signed-32-bit minimum, negative repeated values, and zero singleton. Do not silently broaden the domain beyond int32 while retaining a truncating implementation.

6 / 9

Bitwise AND of Numbers Range — predict before coding

The inclusive range preserves only the common high-bit prefix of its endpoints. Below their highest differing position, the interval necessarily crosses a binary boundary that clears those suffix bits.

Decision: Change the input from a contiguous interval to the sparse set {9,11}. Its smallest and largest values have common prefix 10 in four-bit notation. Would zeroing the suffix still compute the set’s AND?

Presenter notes

Model answer: No. 9=1001 and 11=1011 AND to 1001, or 9. The common-prefix interval rule gives 1000 because the full interval also includes 10=1010, which supplies the missing low zero. The proof uses every integer between the endpoints; it does not extend to an arbitrary sparse subset.

Correctness argument: If left and right are equal, the range contains one value. Otherwise, shift both right until they match, counting s shifts. Their common remaining bits are shared by every number between the endpoints because none crosses a boundary above the highest differing bit. At that differing bit, the interval crosses from a zero block to a one block; it includes a boundary value whose lower suffix is all zero, so every removed suffix position has at least one zero somewhere in the range. AND therefore clears all s suffix positions. Shifting the common prefix back left restores exactly the surviving bits.

Debugging prompt: Test equal endpoints, ranges crossing a power of two, and ranges beginning at zero. Endpoint AND alone is insufficient: 5&7 is 5, but AND of 5,6,7 is 4.

7 / 9

Change the multiplicity promise

In [4,9,2,4,2,7], exactly two values occur once.

Total XOR is 14. Why is that not an answer? Use one set bit to derive two solvable groups.

8 / 9

Reconstruct and transfer

Reconstruct each algorithm from its invariant.

Check width, sign, multiplicity assumptions, and output formatting separately.

9 / 9