Skip to main content

Rebuilding a Number

A number is not a thing you have - it is a thing you wrote down. 1256 is shorthand for 1⋅103+2⋅102+5⋅101+6⋅1001 \cdot 10^3 + 2 \cdot 10^2 + 5 \cdot 10^1 + 6 \cdot 10^0, 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:

n, d = divmod(n, B) # PEEL - take the lowest digit off, shrink n
acc = acc * B + d # BUILD - shift acc up one column, drop d into the gap

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.

ndigit outacc = acc * 10 + d125666125565122652116521peel drains the low endbuild fills the high end
Feed peel straight into build and the digits arrive in the wrong order on purpose. The mismatch is not a bug to route around - it is Reverse Integer.

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:

From base
To base
1. read 1256 in base-10
10311000102220010155010066
= 1256 (decimal)
2. divide 1256 by 2, keep remainders
nn ÷ 2n % 2 (digit)
12566280
6283140
3141570
157781
78390
39191
1991
941
420
210
101
read remainders bottom-to-top10011101000

Peel, and throw the order away​

Narrative

The bare loop. 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; 258 keeps it and adds; 1837 proves the 10 was never special by making it a parameter. 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.

Count Digits in a Number​

4 Approaches
class Solution:
def countDigits(self, n):
digits = 0
while n:
n, rem = divmod(n, 10)
digits += 1
return digits

258. Add Digits​

Easy·
2 Approaches
class Solution:
def addDigits(self, num: int) -> int:
if num // 10 == 0:
return num
total = 0
while num:
num, rem = divmod(num, 10)
total += rem
return self.addDigits(total)

1837. Sum of Digits in Base K​

Easy·
class Solution:
def sumBase(self, n: int, k: int) -> int:
total = 0
while n:
n, rem = divmod(n, k)
total += rem
return total

Peel, when the order does matter​

Narrative

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.

Only two things change between these four problems: the base, and the table you index the remainder into. 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.

Decimal to binary​

4 Approaches
import collections
 
 
class Solution:
def decToBinary(self, n):
ans = collections.deque()
while n:
n, rem = divmod(n, 2)
ans.appendleft(str(rem))
return "".join(ans)

504. Base 7​

Easy·
class Solution:
def convertToBase7(self, num: int) -> str:
if num == 0:
return "0"
neg = num < 0
num = abs(num)
res = collections.deque()
while num:
num, rem = divmod(num, 7)
res.appendleft(str(rem))
if neg:
res.appendleft("-")
return "".join(res)

405. Convert a Number to Hexadecimal​

Easy·
class Solution:
def toHex(self, num: int) -> str:
if num == 0:
return "0"
if num < 0:
num = 2**32 + num
res = collections.deque()
hex_arr = "0123456789abcdef"
while num:
num, rem = divmod(num, 16)
res.appendleft(hex_arr[rem])
return "".join(res)

168. Excel Sheet Column Title​

Easy·
class Solution:
def convertToTitle(self, columnNumber: int) -> str:
col = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
res = collections.deque()
while columnNumber:
columnNumber, rem = divmod(columnNumber - 1, 26)
res.appendleft(col[rem])
return "".join(res)

Build, when someone else supplies the digits​

Narrative

The other primitive, alone. Here 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. 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. 129 and 1022 move the accumulator onto a DFS path and differ from each other 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. Both also undo the build on the way back up (cur //= B), which is a peel used as an unwind.

171. Excel Sheet Column Number​

Easy·
class Solution:
def titleToNumber(self, columnTitle: str) -> int:
col = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
col = {char: idx + 1 for idx, char in enumerate(col)}
total = 0
for char in columnTitle:
total = total * 26 + col[char]
return total

1290. Convert Binary Number in a Linked List to Integer​

Easy·
2 Approaches · 2 patterns
Borrowed from Linked List / One Pass - shown here in full
FIG. CONVERT BINARY NUMBER IN A LINKED LIST T● INTERACTIVE
visualization loads as you reach it
def getDecimalValue(head):
number = 0
curr = head
while curr:
number = number * 2 + curr.val
curr = curr.next
return number
49051cur = 4cur = 49cur = 40 (leaf)cur = 495cur = 491down: cur = cur * 10 + node.valup: cur //= 10
129 on [4,9,0,5,1]. The accumulator is built on the way down and peeled on the way back up, so it always holds the digits of the path you are currently standing on - 495 + 491 + 40 = 1026.

129. Sum Root to Leaf Numbers​

Medium·

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.

3 Approaches
FIG. SUM ROOT TO LEAF NUMBERS● INTERACTIVE
visualization loads as you reach it
def sumNumbers(self, root: Optional[TreeNode]) -> int:
def recursion(node):
nonlocal total, cur_decimal
if node:
cur_decimal = 10 * cur_decimal + node.val
if not node.left and not node.right:
total += cur_decimal
recursion(node.left)
recursion(node.right)
cur_decimal //= 10
 
cur_decimal = total = 0
recursion(root)
return total

1022. Sum of Root To Leaf Binary Numbers​

Easy·

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.

3 Approaches
FIG. SUM OF ROOT TO LEAF BINARY NUMBERS● INTERACTIVE
visualization loads as you reach it
def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
def recursion(node):
nonlocal total, cur_binary
if node:
cur_binary = 2 * cur_binary + node.val
if not node.left and not node.right:
total += cur_binary
recursion(node.left)
recursion(node.right)
cur_binary //= 2
 
cur_binary = total = 0
recursion(root)
return total

Peel and build in the same loop​

Narrative

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. 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. 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.

7. Reverse Integer​

Medium·
class Solution:
def reverse(self, n: int) -> int:
res = 0
neg = n < 0
if neg:
n = -n
while n:
last_bit = n % 10
n = n // 10
res = res * 10 + last_bit
if not -(2**31) <= res <= 2**31 - 1:
return 0
return -res if neg else res

9. Palindrome Number​

Easy·
2 Approaches
class Solution:
def isPalindrome(self, x: int) -> bool:
if x < 0:
return False
original = x
rev = 0
while x:
x, rem = divmod(x, 10)
rev = rev * 10 + rem
return rev == original

190. Reverse Bits​

Easy·
2 Approaches
FIG. 190 BITWISE● INTERACTIVE
visualization loads as you reach it
class Solution:
def reverseBits(self, n: int) -> int:
r = 0
for i in range(32):
r = (r << 1) | (n & 1)
n >>= 1
return r

Digits as a window​

Narrative

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​

Easy·
FIG. 2269 FIND THE K BEAUTY OF A NUMBER● INTERACTIVE
visualization loads as you reach it
class Solution:
def divisorSubstrings(self, num: int, k: int) -> int:
n = int(math.log10(num)) + 1
left = right = 0
ans = sub_num = 0
 
isDivisible = lambda: int(num) % sub_num == 0 if sub_num != 0 else 0
 
while right < n:
# Expansion
while right < n and right - left < k:
power = 10 ** (n - right - 1)
digit = (num // power) % 10
sub_num = sub_num * 10 + digit
right += 1
# Logic
ans += isDivisible()
# Shrinking
sub_num = sub_num % (10 ** (k - 1))
left += 1
return ans

The constraint matrix​

ProblemTitleBasePrimitiveDigits come fromWhat it does about order
GFGthe hubCount Digits10PeelThe numberNothing - the digit is discarded
258from the hubAdd Digits10PeelThe numberNothing - it sums, then recurses to a digital root
1837from 258Sum of Digits in Base KkPeelThe numberNothing - the base is the only delta
GFGfrom 1837Decimal to Binary2PeelThe numberdeque.appendleft - digits are the answer now
504from decimal-to-binaryBase 77PeelThe numberdeque.appendleft
405from 504Convert a Number to Hexadecimal16PeelThe numberdeque.appendleft, plus a digit table past 9
168from 405Excel Sheet Column Title26PeelThe numberdeque.appendleft, and divmod(n - 1, 26) - there is no zero digit
171inverse of 168Excel Sheet Column Number26BuildA string, left to rightNothing to fix - they already arrive high-first
1290from 171Convert Binary Number in a Linked List2BuildA linked list, head firstNothing to fix
129from 1290Sum Root to Leaf Numbers10BuildA root-to-leaf pathNothing to fix; peels on the way back up to unwind
1022from 129Sum of Root to Leaf Binary Numbers2BuildA root-to-leaf path129 with 10 replaced by 2
7peel + buildReverse Integer10BothThe numberExploits it - peel-then-build is the reversal
9from 7Palindrome Number10BothThe numberExploits it, then stops at the midpoint (x > rev)
190from 7Reverse Bits2BothThe numberExploits it over a fixed 32 columns, not until empty
2269all threeFind the K-Beauty of a Number10BothThe number, by column indexBuilds 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.