Compute only what the question can observe

How many trailing decimal zeroes does 25! have?

Decision: Which contributions determine the suffix without constructing the factorial, and why does merely counting multiples of five miss one?

1 / 9

Palindrome Number — predict before coding

Reverse only the suffix until it meets the remaining prefix. This compares decimal structure without constructing the entire reversed integer, whose value might overflow.

Decision: Adapt the half-reversal reasoning to a binary representation with no leading zeroes. Which division, remainder, and middle-bit operations replace the decimal ones? Check binary 1001 and 110.

Presenter notes

Model answer: Replace remainder/division by ten with remainder/division by two, and append a removed bit with rev=2*rev+n%2. For an odd bit count compare n with rev/2. A positive even input ends in zero and cannot be a no-leading-zero binary palindrome. Thus 1001 is a palindrome, while 110 is rejected. The pack’s IsPalindrome function still uses decimal digits.

Correctness argument: After k iterations, rev is the reverse of the k removed low decimal digits and x is the unconsumed high prefix. Removing one digit with modulo/division and appending it to rev preserves that relation. Negative values cannot match a leading minus sign, and a positive trailing zero cannot match a nonzero leading digit, so reject them first. When x<=rev, roughly half the digits have been consumed. Even-length palindromes have x==rev; odd-length palindromes have x==rev/10 because the middle digit is irrelevant. Other inputs fail both comparisons. Within the signed-32-bit domain, reversing only half avoids full-reversal overflow.

Debugging prompt: Test zero, negative values, positive multiples of ten, and odd/even digit counts. Removing the trailing-zero guard can incorrectly accept cases such as 10.

2 / 9

Plus One — predict before coding

The only digits that propagate an increment are a suffix of nines. Once one non-nine absorbs the carry, every earlier digit is already correct.

Decision: A caller keeps digits=[9], calls PlusOne(digits) but ignores its returned slice, then calls PlusOne(digits) again. What does the caller’s original slice contain after each call, and why does this not represent two increments of 9?

Presenter notes

Model answer: The first call zeroes the original slice to [0] and returns a separate [1,0]. The caller ignores that new representation. The second call therefore increments [0] to [1], not ten to eleven. Assigning digits=PlusOne(digits) after each call preserves the current number across a possible change of backing storage and length.

Correctness argument: Working from the least-significant digit, maintain that all processed suffix digits are the correct result and carry is the amount still owed to the next position. Adding carry, storing remainder modulo ten, and updating quotient preserves the invariant. When carry becomes zero, unchanged earlier digits plus the corrected suffix form the full result. If every original digit was nine, all are changed to zero and a new leading one is required. The reference allocates a larger result only in this final case; otherwise it returns the original slice with in-place changes.

Debugging prompt: Test both returned contents and documented mutation. Inputs with leading zeroes retain their width unless a carry grows it; do not normalize them without changing the existing behavior.

3 / 9

Factorial Trailing Zeroes — predict before coding

Every trailing decimal zero comes from a factor 10=2*5. Factorials supply more twos than fives, so count the exponent of five without constructing the factorial.

Decision: Suppose you already know the trailing-zero count of 99!. How much does it increase at 100!, and how much at 101!? Derive the change from the new multiplier instead of recomputing the whole factorial.

Presenter notes

Model answer: 100=4*25 contributes two factors of five, so the count increases by two. 101 contributes none, so the next increase is zero. In general the difference at n! is the exponent of five in n; enough twos remain available. This incremental view agrees with the layer-sum formula while exposing why some steps make no change and powers of five make larger jumps.

Correctness argument: Every multiple of five contributes at least one factor five, giving floor(n/5). Multiples of 25 contribute one additional factor, multiples of 125 another, and so on. Summing floor(n/5^k) counts each factor five exactly once by its depth. Repeatedly dividing n by five produces these terms without explicitly multiplying powers that could overflow. When the quotient reaches zero, no larger power contributes. Since factors two are at least as abundant, this exponent equals the number of complete factors ten and hence trailing zeros.

Debugging prompt: Test immediately before, at, and after powers of five. Counting only multiples of five misses repeated factors. n=0 correctly gives zero trailing zeroes in 0!=1.

4 / 9

Sqrt(x) — predict before coding

The predicate mid²<=x changes from true to false over nonnegative mid. Find its last true value, retaining a feasible answer while narrowing the remaining search.

Decision: A learner returns immediately at the first midpoint satisfying mid²<=x. With the stated interval [0,x] and x=35, trace until that first feasible midpoint. Is it the required answer?

Presenter notes

Model answer: The first midpoints are 17 (too large), 8 (too large), and 3 (feasible). Returning 3 is wrong: the floor square root is 5. Feasibility only establishes a candidate, so record ans=3 and search above it. Continue with midpoint 5, then reject 6; 25<=35<36 is the final certificate.

Correctness argument: Maintain ans as a tested value with ans²<=x and an interval containing any larger feasible candidate. If mid²<=x, midpoint is feasible and every smaller index is no better; record mid and search above it. Otherwise every value at least mid is infeasible, so search below. The interval strictly shrinks. When exhausted, ans is feasible and no larger candidate is feasible, so ans²<=x<(ans+1)². Multiplication is performed in int64; with x<=2^31-1, even the largest tested midpoint squared fits signed 64-bit.

Debugging prompt: Test perfect squares and their immediate neighbors, including the upper signed-32-bit boundary. A floating approximation without integer correction can misclassify a boundary.

5 / 9

Pow(x, n) — predict before coding

Write the exponent in binary. Squaring moves to the next power-of-two contribution, and an odd low bit says to multiply that contribution into the result.

Decision: A refactor squares the current base before checking the exponent’s low bit. Give the smallest positive exponent that exposes the change, using base 3. Which identity did the reordered update fail to preserve?

Presenter notes

Model answer: Exponent 1 should return 3. Squaring first changes the only contribution to 9 before it can be multiplied into the result. The preserved product is result*currentBase^remainingExponent; consume an odd current factor before replacing the base by its square and halving the remaining exponent.

Correctness argument: After handling a negative exponent by reciprocating the base, maintain result * base^exp equal to the desired power in exact arithmetic. If exp is odd, multiply one base into result; the remaining even exponent can be halved while squaring base. If exp is even, square and halve directly. Thus the invariant is preserved and exp decreases to zero in logarithmically many shifts. The exponent is widened to int64 before negating, so the minimum signed-32-bit exponent can be represented positively. Actual float64 multiplication rounds, so the arithmetic identity describes the algorithm, not exact real-number output for every input.

Debugging prompt: Test exponent zero, negative exponents, base -1 with odd/even exponents, and the minimum allowed exponent. Do not promise finite results for arbitrary bases: float overflow, underflow, and division by zero follow floating-point behavior.

6 / 9

Max Points on a Line — predict before coding

Anchor one point and group other points by an exact normalized direction. Rational slope keys avoid floating equality errors, and duplicate coordinates must be counted separately from direction.

Decision: An anchor is (0,0), with other points (1,1), (-1,-1), and (-1,1). A key built from (abs(dx),abs(dy)) puts all three in one bucket. Which points actually share a line, and how should sign normalization differ?

Presenter notes

Model answer: (1,1) and (-1,-1) share the line y=x with the anchor; (-1,1) lies on y=-x. Taking both absolute values erases the slope’s sign and falsely counts four collinear points. Divide by gcd, then flip both signs together when necessary, preserving their relative sign. The valid maximum here is three.

Correctness argument: For a fixed anchor, every nonduplicate point on one line has proportional (dx,dy). Normalize sign and divide by gcd so equivalent directions share one key, treating vertical and horizontal lines consistently. Distinct normalized directions correspond to distinct lines through the anchor. Duplicate coordinates lie on every such line, so add their count plus the anchor to the largest direction bucket. Considering each anchor reaches an anchor on every candidate maximum line; using only later points still counts the full line when its earliest-index point is the anchor. If all points coincide, the duplicate count plus one yields the correct total.

Debugging prompt: Test vertical/horizontal lines, opposite directions, duplicate points, and large coordinates. On the supported 64-bit target, differences of two signed-32-bit coordinates fit int; computing a cross product in the same signed width could still overflow.

7 / 9

Change the output base

How many trailing zeroes does 10! have in base 12?

Factor the base, derive the limiting contribution, and explain why counting fives would be wrong.

8 / 9

Reconstruct and transfer

For each technique, name the representation and its numeric bounds.

Distinguish exact integer logic, floating-point approximation, and preserved mutation.

9 / 9