Rebuilding a Number
A number is not a thing you have - it is a thing you wrote down. 1256 is
shorthand for , and the only
reason the base is 10 is that nobody wrote it next to the digits. Bit Basics
covers that groundwork
and this page assumes it.
What it gives you is two primitives, and they are the whole chain:
They are inverses, and they disagree about direction. Peel hands you digits least-significant first. Build wants them most-significant first. Every problem below is a choice of base, a choice of which primitive, and an answer to that disagreement - ignore it, undo it with a deque, or exploit it on purpose to reverse a number.
Change the base and nothing about that picture changes except the column weights. Convert something and watch both halves run - the decode phase is build, the encode phase is peel:
| n | n ÷ 2 | n % 2 (digit) |
|---|---|---|
| 1256 | 628 | 0 |
| 628 | 314 | 0 |
| 314 | 157 | 0 |
| 157 | 78 | 1 |
| 78 | 39 | 0 |
| 39 | 19 | 1 |
| 19 | 9 | 1 |
| 9 | 4 | 1 |
| 4 | 2 | 0 |
| 2 | 1 | 0 |
| 1 | 0 | 1 |
Peel, and throw the order away
When the answer is a count or a sum, digit order is irrelevant, so the direction problem never arises and divmod is the entire
solution. Count Digits is the skeleton with the digit discarded.
Count Digits in a Number
Count Digits in a Number
GeeksforGeeksDigit-Extraction Loop
258 keeps the skeleton and adds. Note what 258 does after the loop: it recurses until one digit is left, which has a closed
form - 1 + (n - 1) % 9, the digital root. That is the first hint that a peel loop is arithmetic and not just bookkeeping.
258. Add Digits
Digit-Sum Loop
1837 proves the 10 was never special by making it a parameter.
1837. Sum of Digits in Base K
Peel, when the order does matter
Same loop, now the output is the digits themselves.
Peeling emits them backwards, so each of these pays to undo it: collections.deque with
appendleft puts the newest digit in front for free, which is why the house
idiom here is a deque and not a list plus a reverse.
Decimal to binary
Decimal to binary
GeeksforGeeksDigit-by-Digit Rebuild
Only two things change between these four problems: the base, and the table you index the remainder into.
504. Base 7
Only the base and the table you index the remainder into change.
405. Convert a Number to Hexadecimal
168 is the one worth slowing down for - Excel
columns are 1-indexed (A is 1, not 0) and there is no digit for zero, so it
peels divmod(n - 1, 26). That - 1 is the whole problem; everything else is
base conversion you have already written three times.
168. Excel Sheet Column Title
Build, when someone else supplies the digits
The other primitive, alone. The digits arrive most-significant first
from an external source - a string, a linked list, a path down a tree - so
there is nothing to reverse and acc = acc * B + d runs unchanged.
171 is 168 read backwards and belongs beside it.
171. Excel Sheet Column Number
1290 is the same line at
B = 2, walking a list instead of a string, and is usually written
(acc << 1) | node.val - identical arithmetic.
1290. Convert Binary Number in a Linked List to Integer
Mathematical
Borrowed from Linked List ↗129 moves the accumulator onto a DFS path. It also undoes the build on the way back up (cur //= B), which is a peel used as an unwind.
129. Sum Root to Leaf Numbers
Each root-to-leaf path spells a decimal number (most significant digit at the root). Carry the running value down with cur_decimal = 10 * cur_decimal + node.val, and add it to the total whenever a leaf is reached. This mirrors the binary version (1022), swapping base 2 for base 10.
DFS (Recursive)
1022 differs from 129 only in the base, which is the cleanest evidence on this page that B is a parameter: the two solutions
are byte-for-byte identical apart from 10 and 2.
1022. Sum of Root To Leaf Binary Numbers
Each root-to-leaf path spells a binary number (most significant bit at the root). Carry the running value down the path with cur_binary = 2 * cur_binary + node.val, and add it to the total whenever a leaf is reached.
DFS (Recursive)
Peel and build in the same loop
Now run both, and the direction mismatch becomes the feature. Peel off
n's lowest digit and immediately build it onto res: the last digit out is
the first digit in, so res comes out reversed. That is not a side effect to
work around, it is the algorithm.
7 is the statement of it, plus an overflow check Python only needs because the problem imposes a 32-bit range.
7. Reverse Integer
9 reuses 7 wholesale - reverse and compare -
then the second solution notices you only need half: stop once rev >= x
and compare rev == x or x == rev // 10, the // 10 dropping the odd middle
digit.
9. Palindrome Number
Full Reversal
190 is the same loop at B = 2 written in bit form, r = (r << 1) | (n & 1),
and looping a fixed 32 times rather than until n runs out - because leading
zeros are significant when the width is declared.
190. Reverse Bits
Bit by Bit
Digits as a window
The capstone, because it needs all three moves at once. 2269 slides a
k-digit window across num and asks how many of those windows divide it, and
it does it without ever building a string.
Reading a digit by index is (num // 10**p) % 10 - peel, but skipping
straight to column p. Extending the window right is the plain build,
sub_num * 10 + digit. And shrinking from the left is the move nothing else
here needs: sub_num % 10 ** (k - 1) deletes the leading digit, because
modulo by a power of the base is exactly "keep the low columns". That is the
full vocabulary - peel, build, and truncate - in one loop.
2269. Find the K-Beauty of a Number
Sliding Window
The constraint matrix
| Problem | Base | Primitive | Digits come from | What it does about order |
|---|---|---|---|---|
| count-digits Count Digitsthe hub | 10 | Peel | The number | Nothing - the digit is discarded |
| 258 Add Digitsfrom count-digits | 10 | Peel | The number | Nothing - it sums, then recurses to a digital root |
| 1837 Sum of Digits in Base Kfrom 258 | k | Peel | The number | Nothing - the base is the only delta |
| dec-to-bin Decimal to Binaryfrom 1837 | 2 | Peel | The number | deque.appendleft - digits are the answer now |
| 504 Base 7from dec-to-bin | 7 | Peel | The number | deque.appendleft |
| 405 Convert a Number to Hexadecimalfrom 504 | 16 | Peel | The number | deque.appendleft, plus a digit table past 9 |
| 168 Excel Sheet Column Titlefrom 405 | 26 | Peel | The number | deque.appendleft, and divmod(n - 1, 26) - there is no zero digit |
| 171 Excel Sheet Column Numberfrom 168 | 26 | Build | A string, left to right | Nothing to fix - they already arrive high-first |
| 1290 Convert Binary Number in a Linked Listfrom 171 | 2 | Build | A linked list, head first | Nothing to fix |
| 129 Sum Root to Leaf Numbersfrom 1290 | 10 | Build | A root-to-leaf path | Nothing to fix; peels on the way back up to unwind |
| 1022 Sum of Root to Leaf Binary Numbersfrom 129 | 2 | Build | A root-to-leaf path | 129 with 10 replaced by 2 |
| 7 Reverse Integerfrom count-digits | 10 | Both | The number | Exploits it - peel-then-build is the reversal |
| 9 Palindrome Numberfrom 7 | 10 | Both | The number | Exploits it, then stops at the midpoint (x > rev) |
| 190 Reverse Bitsfrom 7 | 2 | Both | The number | Exploits it over a fixed 32 columns, not until empty |
| 2269 Find the K-Beauty of a Numberfrom 7 | 10 | Both | The number, by column index | Builds right, truncates left with % 10 ** (k - 1) |
Read the last two columns together. The base column is noise - it changes on almost every row and changes nothing about the code. The work is always in the last column: whether you can ignore the direction peel forces on you, have to spend a deque undoing it, or can arrange for it to be the answer.