Digit and Number Math
What is this?
These tricky problems look like they need a loop or simulation, but each one hides a number identity that makes the loop disappear. The single insight is to stop simulating and count the right thing — a digital root that's just a value mod 9, a count of one prime factor, or a single greedy digit swap. Recognizing the closed-form shortcut is the whole game.
💡 Fun fact: Repeatedly summing a number's digits until one remains always equals the number modulo 9 — because every power of ten leaves a remainder of 1 when divided by 9, so the digits and the whole number are congruent mod 9.
🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: Many "number" problems hide a closed-form identity. Instead of simulating the process, you spot the underlying arithmetic — a mod-9 root, a count of a single prime factor, a greedy digit choice — and the loop collapses to a formula or a single pass.
The pattern
The reframe here is stop simulating, start counting the right thing. Repeatedly summing digits until one remains is just the value modulo 9 (the digital root), because each power of ten is congruent to 1 mod 9. The whole iterative process becomes one expression.
The same instinct applies to factorials: trailing zeros come from factors of ten, and tens are scarcer in their 5 than their 2, so you only count how many 5s the factorial contributes — including the extra 5s from 25, 125, and so on. You never build the huge number.
For rearranging digits, the move is greedy with the right target: scan for the leftmost digit that can be improved, and swap it with the largest later digit (preferring the rightmost occurrence of that largest digit to maximize the gain). One swap, chosen carefully, beats searching all pairs. The thread throughout: find the identity or the single decisive move.
The problems
- Add Digits — the repeated digit sum is the digital root, computable as
1 + (n-1) % 9for positiven; no looping. - Factorial Trailing Zeroes — count factors of 5 across the factorial (
n/5 + n/25 + n/125 + ...), since 2s always outnumber 5s. - Maximum Swap — greedily find the leftmost digit smaller than some later digit, then swap it with the rightmost occurrence of the largest such digit.
Key takeaways
- Look for the identity — digital root is mod 9, not a loop.
- Count the scarce factor — trailing zeros track 5s, not 10s.
- Greedy needs the right target — leftmost improvable, rightmost-largest.
- Don't build the big number — reason about its factors instead.
Maximum Swap
Core idea: You get at most one swap of two digits, and you want the biggest number possible. The most valuable place to make a number bigger is the leftmost digit you can improve, because that position carries the highest place value. So scan from left to right and ask, at each digit: does any strictly larger digit appear somewhere to my right? The first time the answer is yes, swap this digit with the largest such later digit — and if that large digit repeats, use its rightmost occurrence so the big digit lands as far left as possible while pushing a small digit as far right as possible. To make those lookups instant, first record, for each digit value
0–9, the last index where it appears. Then one left-to-right pass finds the swap. That's O(d) in the number of digits.
The problem, rephrased
You are handed a price tag that reads, say, 2736, and a clerk tells you: "You may, if you like, peel off exactly two digits and swap their positions — but only one such swap, and only if it helps." Your job is to walk away with the largest number you can possibly show. For 2736, swapping the 2 and the 7 gives 7236, which is the best you can do. Return that maximized number.
This is LeetCode 670 — Maximum Swap.
| Input | Means | Output |
|---|---|---|
num = 2736 |
swap the 2 and the 7 |
7236 |
num = 9973 |
already as large as one swap allows | 9973 |
num = 98368 |
swap the 3 with the later 8 |
98863 |
The number is non-negative and (per LeetCode) fits in a 32-bit int. "At most one swap" is the whole game: you don't get to fully sort the digits — you get one exchange, so you must spend it where it buys the most.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson