Math

Reader guide and study workflow · Complete course map

How many trailing decimal zeroes does 25! have? Multiplying 1 through 25 and inspecting the result is a correct model, but it constructs much more information than the query needs. The decimal digits before the zero suffix are irrelevant. A trailing zero contributes a factor ten, and ten is 2×5.

The first thinking move is therefore to change the representation: count the prime contributions that determine the answer instead of constructing the huge integer.

Count contributions at the scale where they are local

Every multiple of five contributes at least one five: 5,10,15,20,25. The last number contributes another, so the answer is six, not five. At larger sizes, multiples of 125 contribute a third five, and so on. Twos are at least as abundant as fives in a factorial, so fives limit the complete tens.

Repeated integer division produces the layer counts without multiplying powers of five:

count=0
while n>0:
    n=n/5
    count=count+n

After k iterations, count is the sum of the first k contribution layers of the original n. When the remaining quotient is zero, all layers have been counted. This is why the loop is logarithmic and why it does not need a big-integer factorial.

Digit problems apply the same “keep only the required information” principle differently. Plus One needs a carry and the unprocessed prefix; the first non-nine absorbs the carry. Palindrome Number needs the unconsumed prefix and a reversed suffix, stopping when they meet. Work the concrete odd/even and mutation traces below before treating either as a recipe.

Ask for a certificate, not a plausible approximation

For an integer square root y, the certificate is y²<=x<(y+1)². A floating value close to sqrt(x) does not establish those inequalities. Binary search uses the monotone feasibility predicate and retains its best tested answer while looking for a larger one.

Arithmetic used to check the certificate must be valid too. This pack bounds x by 2^31-1, so converting each midpoint to int64 before multiplication is sufficient. A division-based check mid<=x/mid avoids multiplication but needs mid>0. Neither expression is a universal replacement without its preconditions.

For powers, repeatedly multiplying x n times repeats work. The exponent’s binary expansion lets one squared base represent successively 1,2,4,8,... multiplications. Keep result * currentBase^remainingExponent equal to the desired power in exact arithmetic. If the remaining exponent is odd, consume one base into result; then square the base and halve the remainder. Negative exponents first invert the base and safely form the exponent magnitude. Floating-point rounding remains part of the result contract.

Canonicalize objects before comparing them

Points define a line through an anchor by a direction, not by a floating approximation. Directions (1,2), (2,4), and (-3,-6) are proportional and should occupy one bucket. Dividing by gcd and choosing one sign convention makes their exact keys equal.

The pair (0,0) is different: a duplicate anchor has no direction at all but lies on every line through that coordinate. Count it separately. This illustrates a useful question for any normalization: which inputs do not have the representation you are trying to normalize?

Coordinate bounds also constrain intermediates. Differences of signed-32-bit coordinates may need 33 signed bits, so the supplied MaxPoints reference expects a 64-bit int target. Cross products for a testing oracle can need still more space. Correct formulas do not by themselves justify a chosen machine type.

Transfer: the output base changes the counting problem

How many trailing zeroes would 10! have when written in base 12? Factor 12 first, then determine which prime contribution limits the result. Why would counting only factors of five now answer the wrong question?

Model answer: divide available contributions by required multiplicity

12=2²×3. The exponent of two in 10! is floor(10/2)+floor(10/4)+floor(10/8)=5+2+1=8. The exponent of three is floor(10/3)+floor(10/9)=3+1=4. Each factor twelve consumes two twos and one three, so the number of complete twelves is min(floor(8/2),4)=4.

The decimal algorithm counts fives because ten needs one two and one five, with twos available in excess. That reasoning belongs to base ten. The transferable rule is to factor the output base and compare available prime exponents with the multiplicities it requires, not to memorize “divide by five.” The implemented TrailingZeroes exercise keeps its decimal contract.

For every shortcut, identify the expensive representation, the smaller information sufficient for the answer, its invariant or certificate, and the numeric domain in which the implementation preserves that reasoning. “A formula exists” is the beginning of an explanation, not the end.

Prerequisites and readiness

Know decimal division/remainder, binary search boundaries, factors and gcd, and finite-width integer versus floating-point arithmetic. Be able to distinguish floor from rounding and a coordinate difference from a slope.

Reasoning workshop: change representation before doing expensive arithmetic

Digits: discard only what you can reconstruct

For palindrome 12321, the half-reversal states (remaining, reversed) are (1232,1), (123,12), and (12,123). At the crossing point, the middle digit can be removed from the reversed half: 123/10=12. For an even-length palindrome, the two halves compare directly. A positive number ending in zero cannot be a palindrome because its decimal representation does not begin in zero; handle 0 separately as a palindrome.

Plus One has a different suffix invariant. For [1,2,9,9], process the trailing nines into zeroes, increment 2 to 3, and stop. The leading 1 requires no work. For [9,9], the old slice becomes [0,0] and a new [1,0,0] is returned. Merely checking the return value misses this existing mutation contract.

Factors: count contributions instead of constructing the number

Predict how the trailing-zero count changes from 124! to 125!, without building either factorial. Complete the contribution layers for 125, then explain why the count jumps by more than one even though n increased by one.

Model answer: charge every factor in the new multiplier

For 124, the layers are 24,4,0, totaling 28. For 125, they are 25,5,1, totaling 31. Multiplying by 125 contributes three additional fives because 125=5³, so the difference is 3. Counting only newly encountered multiples of five would miss two of them.

Repeated division computes floor(n/5), floor(n/25), and so on without creating n! or multiplying an ever-growing power of five. Why count fives rather than twos? Every five has an available two in a factorial; twos occur more frequently. Decimal zeroes count complete pairs 2*5, so the rarer prime limits the total. A changed base requires factoring that base and accounting for the required prime multiplicities, as in the transfer exercise above.

Search: state the certificate for the returned integer

For x=15, y=3 is certified by y²<=x<(y+1)². “Close to sqrt(x)” is not the contract. A division-based search must not divide by midpoint zero: handle x<2, then search from 1. The actual Go reference instead widens products to int64; under its signed-32-bit x bound those products fit. These are two valid overflow-avoidance techniques, not interchangeable snippets without their preconditions.

Powers: consume exponent bits while preserving the product

For exponent 13=1101 in binary, multiply base powers 1,4,8. The maintained exact-arithmetic identity is result*base^remaining = target. For an odd exponent, move one base into result; squaring base and halving the remaining exponent then preserves the identity. Negative exponents invert the base, but the minimum allowed signed-32-bit exponent must be widened before negation.

The identity is a correctness model, not a promise of exact real arithmetic from float64. Multiplication rounds; extreme magnitudes can overflow or underflow. The API returns 1 for exponent zero, including 0^0. Those are concrete implementation semantics rather than missing mathematical exceptions to invent silently.

Lines: canonicalize exact directions

Fix anchor (0,0). Directions (1,1), (2,2), and (-3,-3) represent the same undirected line. Divide both coordinates by their gcd and normalize sign. Vertical and horizontal directions need consistent canonical forms. A duplicate point (0,0) has direction (0,0), which cannot be reduced to a meaningful slope; count it separately and add it to every candidate line through the anchor.

A floating slope is unnecessary and makes equality fragile. An exact reduced pair solves equality without dividing coordinates. Signed-32-bit coordinate differences require the supported 64-bit int target at extremes; a cross-product oracle needs wider arithmetic still. The new tests compute their collinearity oracle with arbitrary-precision integers rather than duplicating the reference’s gcd implementation.

Reconstruction lab and answer key

Palindrome Number

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.

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.

Plus One

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?

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.

Factorial Trailing Zeroes

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.

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.

Sqrt(x)

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?

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.

Pow(x, n)

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?

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.

Max Points on a Line

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?

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.

Problems in this module

• Palindrome Number
• Plus One
• Factorial Trailing Zeroes
• Sqrt(x)
• Pow(x, n)
• Max Points on a Line

Interactive checkpoint

Open the Math quiz. The questions use exact, objectively gradeable answers. Work the reasoning drills above before opening their model answers.

Earlier-edition deep links

These anchors preserve links to headings from the original files. They do not reinstate superseded explanations.

Learner experience: how to make this topic stick

The moves to recognize

How to practice without turning it into grind

Debugging instincts to build

A small way to make it memorable

Earlier-edition pattern links

The opening now derives the choices above before naming individual recipes. These headings preserve prior bookmarks.

Pattern A: Palindrome by reversing half

Continue with the current reasoning workshop.

Pattern B: Digit array increment

Continue with the current reasoning workshop.

Pattern C: Count factors of 5

Continue with the current reasoning workshop.

Pattern D: Integer square root

Continue with the current reasoning workshop.

Pattern E: Fast exponentiation

Continue with the current reasoning workshop.

Pattern F: Slope normalization with GCD

Continue with the current reasoning workshop.

When to use Math tricks (checklist)

Continue with the current reasoning workshop.

Common failures (checklist)

Continue with the current reasoning workshop.

Problem mapping

Continue with the current reasoning workshop.