Skip to main content

Math

How to know which math to use​

A quick cheat sheet for deducing the right counting logic:

  • Use powers (NxN^x): when every single item makes an independent choice from NN options. Example: each of xx merged intervals independently picks one of N=2N = 2 groups.
  • Use combinations (nCrnCr): when you pick a specific number of items from a larger pool and order doesn't matter. Example: "how many ways can you choose exactly 3 intervals out of the total to form a single group?"
  • Use permutations (nPrnPr): when you arrange items in a specific sequence. Example: "in what order can these intervals be processed?"

Worked example: 3 intervals, 2 groups​

Every interval independently picks group A or B. The choice tree doubles at each level, so the leaf count is 2×2×2=23=82 \times 2 \times 2 = 2^3 = 8.

AAAAABABAABBBAABABBBABBBinterval 1 → 2interval 2 → 4interval 3 → 8AB
Each level is one interval making an independent 2-way choice, so the number of outcomes doubles: 2, 4, 8.

Change the question and the formula changes with it: "choose exactly 2 of the 3 intervals for group A" is 3C2=33C2 = 3 (the leaves with exactly two A's), and "in what order are the 3 intervals processed" is 3P3=63P3 = 6.

Factorials​

Trailing zeroes in factorial​

Easy·
Explanation

A trailing zero is produced by a factor of 10 = 2 * 5. In N! there are always far more factors of 2 than of 5, so the number of trailing zeroes equals the number of factors of 5.

Counting factors of 5 means summing how many multiples of 5, 25, 125, ... are at most N:

fives = N//5 + N//25 + N//125 + ...

Each multiple of 25 contributes a second factor of 5, each multiple of 125 a third, and so on - which is exactly what the running divisor *= 5 captures.

Worked example (N = 100):

  • 100 // 5 = 20
  • 100 // 25 = 4
  • 100 // 125 = 0 - loop stops.
  • Total trailing zeroes: 24.
Analysis
Time
O(log N)
  • The divisor multiplies by 5 each iteration, so the loop runs about log_5(N) times.
Space
O(1)
  • Only a few integer accumulators are used.
FIG. TRAILING ZEROES● INTERACTIVE
visualization loads as you reach it
class Solution:
def trailingZeroes(self, N):
fives = 0
divisor = 5
while N // divisor:
fives += N // divisor
divisor *= 5
return fives

Digit Counting & Sums​

Count Digits in a Number​

4 Approachesclick to switch
Explanation

Peel off one digit at a time with divmod(n, 10), incrementing a counter each pass, until n reaches 0.

Analysis
Time
O(log N)
  • The loop runs once per digit of n, and n has O(log N) digits.
Space
O(1)
  • Only a counter and the shrinking n are kept.
FIG. COUNT DIGITS LOOP● INTERACTIVE
visualization loads as you reach it
class Solution:
def countDigits(self, n):
digits = 0
while n:
n, rem = divmod(n, 10)
digits += 1
return digits

Count Commas in Range​

Easy·
Explanation

Writing a number with thousands separators only inserts a comma once the number reaches 4 digits, i.e. 1000 and up (n's constraints keep every value under a million, so there's never more than one comma). Numbers 1..999 contribute zero commas; every number from 1000 to n contributes exactly one. That's n - 999 numbers, floored at 0.

Analysis
Time
O(1)
  • A single subtraction and comparison, no iteration.
Space
O(1)
  • No auxiliary storage is used.
class Solution:
def countCommas(self, n: int) -> int:
return max(n - 999, 0)

258. Add Digits​

Easy·
2 Approachesclick to switch
Explanation

Same digit-extraction loop as Sum of Digits in Base K: peel off each digit with divmod(num, 10) and accumulate into total. If that single pass didn't reduce num to one digit, recurse on total and repeat until it does.

Analysis
Time
O(log N)
  • Each recursive call sums O(log N) digits, and the digit sum shrinks fast enough that only a handful of recursive calls are ever needed.
Space
O(log N)
  • The recursion stack holds one frame per call until num collapses to a single digit.
FIG. ADD DIGITS LOOP● INTERACTIVE
visualization loads as you reach it
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·
Explanation

Same digit-extraction loop as Base 7: peel off the last base-k digit with divmod(n, k) and repeat until n is 0. Instead of collecting digits into an output, just accumulate them into total.

Analysis
Time
O(log N)
  • One iteration per base-k digit of n, so the loop runs O(log_k N) times.
Space
O(1)
  • Only a single running total is kept.
FIG. SUM OF DIGITS IN BASE K● INTERACTIVE
visualization loads as you reach it
class Solution:
def sumBase(self, n: int, k: int) -> int:
total = 0
while n:
n, rem = divmod(n, k)
total += rem
return total

3483. Unique 3-Digit Even Numbers​

Easy·
Explanation

Brute-force over the output space instead of the input: loop every even 3-digit number num from 100 to 998, split it into digits i, j, k, and check whether the multiset {i, j, k} fits inside the available digits.

f = Counter(digits) tallies how many of each digit value are on hand. The membership check relies on booleans being ints in Python (True == 1, False == 0), so each comparison answers "do I still have an unused copy of this digit, after the earlier positions already claimed theirs?"

  • f[i] > 0 needs at least one copy of i.
  • f[j] > (i == j) needs f[j] > 0 normally, but if j is the same value as i, the threshold becomes f[j] > 1, since i already spent one copy of that digit.
  • f[k] > (i == k) + (j == k) needs a threshold of 0, 1, or 2 depending on how many of i and j already used up that same digit value. num = 777 needs f[7] > 0 + 1 + 1 = 2, i.e. three 7s available.

This avoids mutating and restoring a frequency array (f[i] -= 1 ... f[i] += 1) around each check, trading that bookkeeping for the arithmetic trick above.

Analysis
Time
O(1)
  • The outer loop always runs over the fixed range of 450 even numbers between 100 and 998, doing O(1) work per iteration, regardless of len(digits).
Space
O(1)
  • The Counter holds at most 10 distinct digit keys.
FIG. UNIQUE 3 DIGIT EVEN NUMBERS● INTERACTIVE
visualization loads as you reach it
class Solution:
def totalNumbers(self, digits: List[int]) -> int:
count = 0
f = Counter(digits)
for num in range(100, 1000, 2):
i, rem = divmod(num, 100)
j, k = divmod(rem, 10)
if f[i] > 0 and f[j] > (i == j) and f[k] > (i == k) + (j == k):
count += 1
return count

Base Conversion​

Decimal to binary​

4 Approachesclick to switch
Explanation

Same digit-extraction loop as Base 7, just base 2 instead of 7: peel off the last bit with divmod(n, 2) and push it to the front of a deque until n is 0.

Analysis
Time
O(log N)
  • One iteration per bit of n, so the loop runs O(log₂ N) times.
Space
O(1)
  • The output deque holds a number of digits proportional to log₂ N, bounded for any fixed-width integer.
FIG. DECIMAL TO BINARY● INTERACTIVE
visualization loads as you reach it
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·
Explanation

Same digit-extraction loop as Convert a Number to Hexadecimal, just base 7 instead of 16: peel off the last digit with divmod(num, 7) and push it to the front of a deque until num is 0.

The sign is handled separately: take abs(num) up front, run the loop on the magnitude, then prepend "-" at the end if the original was negative.

Analysis
Time
O(log N)
  • One iteration per base-7 digit of num, so the loop runs O(log₇ N) times.
Space
O(log N)
  • res accumulates one digit per iteration, so it grows to O(log₇ N) size.
FIG. BASE 7● INTERACTIVE
visualization loads as you reach it
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·
Explanation

Peel off the last hex digit of num with divmod(num, 16), map the remainder through hex_arr, and push it to the front of a deque. Repeat until num is 0.

Negative numbers are handled by first converting to their 32-bit two's-complement value (2**32 + num), so the same divmod loop produces the correct unsigned hex digits.

Analysis
Time
O(log N)
  • One iteration per hex digit of num, so the loop runs O(log₁₆ N) times, bounded by 8 for a 32-bit integer.
Space
O(1)
  • The output holds at most 8 hex digits regardless of input size.
FIG. CONVERT A NUMBER TO HEXADECIMAL● INTERACTIVE
visualization loads as you reach it
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)

3602. Hexadecimal and Hexatrigesimal Conversion​

Easy·
Explanation

Two conversions, one loop. convert(num, to_base) is the same divmod peel as Base 7 and Convert a Number to Hexadecimal, except the base is inferred from the length of the digit alphabet passed in - len(to_base) is 16 for hexa and 36 for hexatri.

hashmap = {idx: ele for idx, ele in enumerate(to_base)} maps a remainder to its display character, so 10 -> "A" in both alphabets and 35 -> "Z" only in base 36. Since to_base is already a string indexable by position, the dict is just an explicit restatement of to_base[rem].

The answer is convert(n*n, hexa) + convert(n*n*n, hexatri) - the square in base 16 concatenated with the cube in base 36. n >= 1 by the constraints, so the while num loop always runs at least once and never returns an empty string.

Analysis
Time
O(log N)
  • One iteration per output digit: log16(n^2) for the hexadecimal pass plus log36(n^3) for the hexatrigesimal pass. Building each hashmap is O(1) (16 and 36 fixed entries).
Space
O(log N)
  • The deque plus the joined result hold O(log n) characters.
FIG. HEXADECIMAL AND HEXATRIGESIMAL CONVERSION● INTERACTIVE
visualization loads as you reach it
class Solution:
def concatHex36(self, n: int) -> str:
def convert(num: int, to_base: dict) -> str:
ans = collections.deque()
hashmap = {idx: ele for idx, ele in enumerate(to_base)}
while num:
num, rem = divmod(num, len(to_base))
ans.appendleft(hashmap[rem])
return "".join(ans)
 
hexa = "0123456789ABCDEF"
hexatri = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
return convert(n * n, hexa) + convert(n * n * n, hexatri)

171. Excel Sheet Column Number​

Easy·
Explanation

columnTitle is a base-26 number where each letter is a digit from 1 to 26 (A = 1, not 0), read most-significant-first.

Build a lookup from letter to its 1-indexed value, then fold left to right: total = total * 26 + col[char]. This is the same digit-rebuild as decimal string-to-int parsing, just with base 26 and a 1-indexed digit value instead of 0-indexed.

Analysis
Time
O(N)
  • One pass over the N characters of columnTitle.
Space
O(1)
  • The col lookup is a fixed 26-entry table, independent of input size.
FIG. EXCEL SHEET COLUMN NUMBER● INTERACTIVE
visualization loads as you reach it
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

168. Excel Sheet Column Title​

Easy·
Explanation

This is base-26, but the digits are 1-indexed (A = 1 ... Z = 26, no digit 0), so a plain divmod(columnNumber, 26) would misalign at multiples of 26. Subtracting 1 first (columnNumber - 1) shifts the range to 0-indexed before dividing, which is the same trick as Excel Sheet Column Number run in reverse.

Peel off the last letter with divmod(columnNumber - 1, 26), push it to the front of a deque, and repeat until columnNumber is 0.

Analysis
Time
O(log N)
  • One iteration per letter of the output, so the loop runs O(log₂₆ N) times.
Space
O(1)
  • The output holds a bounded number of letters regardless of input size (excluding the returned string itself).
FIG. EXCEL SHEET COLUMN TITLE● INTERACTIVE
visualization loads as you reach it
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)

Number-to-Text Encoding​

12. Integer to Roman​

Medium·
3 Approachesclick to switch
Explanation

List every Roman value (including the subtractive pairs like 900 -> "CM") from largest to smallest. For each one, divmod(num, value) tells you how many times that symbol fits and what's left over - same digit-extraction shape as Sum of Digits in Base K, just against a table of irregular "bases" instead of a fixed one.

Analysis
Time
O(1)
  • The table has a fixed 13 entries, so the loop runs at most 13 times regardless of num.
Space
O(1)
  • The output has a bounded length (at most 15 characters for any valid input).
FIG. INTEGER TO ROMAN GREEDY TABLE● INTERACTIVE
visualization loads as you reach it
class Solution:
def intToRoman(self, num: int) -> str:
digits = [
(1000, "M"),
(900, "CM"),
(500, "D"),
(400, "CD"),
(100, "C"),
(90, "XC"),
(50, "L"),
(40, "XL"),
(10, "X"),
(9, "IX"),
(5, "V"),
(4, "IV"),
(1, "I"),
]
ans = []
for value, symbol in digits:
if num == 0:
break
count, num = divmod(num, value)
ans.append(symbol * count)
return "".join(ans)

13. Roman to Integer​

Easy·
Explanation

Check the two-character slice s[i:i+2] against a table of the six subtractive pairs ("CM", "CD", "XC", "XL", "IX", "IV") first, consuming 2 characters on a hit. Otherwise fall back to the single-character table and consume 1 - the inverse lookup of Integer to Roman's greedy value-symbol table.

Analysis
Time
O(n)
  • Each iteration advances i by 1 or 2, so the loop visits every character of s at most once.
Space
O(1)
  • Both lookup tables have a fixed number of entries regardless of s.
FIG. ROMAN TO INTEGER TWO CHAR LOOKAHEAD● INTERACTIVE
visualization loads as you reach it
class Solution:
def romanToInt(self, s: str) -> int:
hashmap = {
"M": 1000,
"D": 500,
"C": 100,
"L": 50,
"X": 10,
"V": 5,
"I": 1,
}
hashmap_double = {
"CM": 900,
"CD": 400,
"XC": 90,
"XL": 40,
"IX": 9,
"IV": 4,
}
total = 0
i = 0
while i < len(s):
if s[i : i + 2] in hashmap_double:
total += hashmap_double[s[i : i + 2]]
i += 2
elif s[i] in hashmap:
total += hashmap[s[i]]
i += 1
return total

273. Integer to English Words​

Hard·
Explanation

Peel off num in base-1000 groups with divmod(num, 1000), same digit-extraction loop as Convert a Number to Hexadecimal, just base 1000 instead of 16.

Each 3-digit group is spelled out by getFrom3Digit: hundreds place from direct + "Hundred", then the last two digits handled as either a tens word, an 11-19 irregular from ten2twenty, or a tens + ones combo.

Non-zero groups get a scale word (Thousand/Million/Billion) from pos[idx] based on which group index they came from, then everything collected in a deque (front-to-back = most-significant-first) is joined with spaces.

Analysis
Time
O(log num)
  • The while num loop peels off one base-1000 group per iteration via divmod(num, 1000), so it runs O(log num) times (base 1000); each iteration does constant work in getFrom3Digit.
Space
O(1)
  • direct, tens, ten2twenty, and pos are fixed-size lookup tables, and ans holds at most one entry per group - bounded regardless of input, since a 32-bit num has at most 4 groups.
FIG. INTEGER TO ENGLISH WORDS● INTERACTIVE
visualization loads as you reach it
class Solution:
def numberToWords(self, num: int) -> str:
def getFrom3Digit(x):
res = []
first_digit = x // 100
x %= 100
if first_digit > 0:
res.append(direct[first_digit])
res.append("Hundred")
second_digit = x // 10
third_digit = x % 10
if second_digit > 0 and third_digit == 0:
res.append(tens[second_digit])
elif second_digit == 1:
res.append(ten2twenty[third_digit])
else:
if second_digit >= 2:
res.append(tens[second_digit])
if third_digit > 0:
res.append(direct[third_digit])
return res
 
direct = [
"Zero",
"One",
"Two",
"Three",
"Four",
"Five",
"Six",
"Seven",
"Eight",
"Nine",
]
tens = [
None,
"Ten",
"Twenty",
"Thirty",
"Forty",
"Fifty",
"Sixty",
"Seventy",
"Eighty",
"Ninety",
]
ten2twenty = [
None,
"Eleven",
"Twelve",
"Thirteen",
"Fourteen",
"Fifteen",
"Sixteen",
"Seventeen",
"Eighteen",
"Nineteen",
]
if num < 10:
return direct[num]
pos = [None, "Thousand", "Million", "Billion"]
ans = collections.deque()
idx = 0
while num:
num, rem = divmod(num, 1000)
res = getFrom3Digit(rem)
if res:
if idx > 0:
ans.appendleft([pos[idx]])
ans.appendleft(res)
idx += 1
return " ".join(j for i in ans for j in i)

Reversal & Palindromes​

7. Reverse Integer​

Medium·
Explanation

Peel off the last digit of n with n % 10 and n // 10, then rebuild the reversed number one digit at a time with res = res * 10 + last_bit.

The sign is handled separately: negate n up front if it was negative, reverse the positive magnitude, then re-apply the sign at the end.

Since Python ints don't overflow, the 32-bit range check -2**31 <= res <= 2**31 - 1 is done explicitly after the loop instead of relying on overflow to happen naturally.

Analysis
Time
O(log N)
  • One iteration per digit of n, so the loop runs O(log N) times.
Space
O(1)
  • Only a handful of integer accumulators are used.
FIG. REVERSE INTEGER● INTERACTIVE
visualization loads as you reach it
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 Approachesclick to switch
Explanation

Same digit-rebuild loop as Reverse Integer: peel off digits of x with divmod(x, 10) and rebuild them in reverse into rev. x is a palindrome exactly when the fully reversed number equals the original.

Negative numbers can never be palindromes (the - only appears at the front), so they're rejected up front.

Analysis
Time
O(log N)
  • One iteration per digit of x, so the loop runs O(log N) times.
Space
O(1)
  • Only original, x, and rev are tracked.
FIG. PALINDROME NUMBER FULL REVERSAL● INTERACTIVE
visualization loads as you reach it
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

Power Checks​

326. Power of Three​

Easy·
4 Approachesclick to switch
Explanation

Keep dividing n by 3 as long as it divides evenly. If n really is a power of 3, this whittles it all the way down to 1; if any remainder pops up along the way, it never was.

Analysis
Time
O(log N)
  • Each iteration divides n by 3, so the loop runs O(log₃ N) times.
Space
O(1)
  • Only n itself is tracked.
FIG. POWER OF THREE REPEATED DIVISION● INTERACTIVE
visualization loads as you reach it
class Solution:
def isPowerOfThree(self, n: int) -> bool:
if n < 1:
return False
while n % 3 == 0:
n /= 3
return n == 1

1780. Check if Number is a Sum of Powers of Three​

Medium·
3 Approachesclick to switch
Explanation

n is a sum of distinct powers of 3 exactly when its base-3 representation has no digit 2 - every digit is 0 or 1, i.e. each power of 3 is used at most once. This is the same digit-extraction loop as Sum of Digits in Base K and Base 7, but instead of collecting the digit it just checks it: n % 3 == 2 means a digit is unusable, so bail out immediately.

Analysis
Time
O(log N)
  • One iteration per base-3 digit of n, so the loop runs O(log₃ N) times.
Space
O(1)
  • Only n itself is tracked.
FIG. CHECK IF NUMBER IS A SUM OF POWERS OF THREE● INTERACTIVE
visualization loads as you reach it
class Solution:
def checkPowersOfThree(self, n: int) -> bool:
while n > 0:
if n % 3 == 2:
return False
n //= 3
return True

Range Bookkeeping​

598. Range Addition II​

Easy·
Explanation

Every operation increments a rectangle [0, i) x [0, j) starting at the origin. The cell that ends up with the maximum value is always inside every one of those rectangles, so the answer region is just the intersection of all of them: rows 0 to min(i) and columns 0 to min(j). Track the running minimums a and b across ops and return their product.

Analysis
Time
O(len(ops))
  • Each operation is visited once to update the running minimums a and b.
Space
O(1)
  • Only the scalars a and b are kept, regardless of m, n, or the number of operations.
FIG. RANGE ADDITION II SHRINK● INTERACTIVE
visualization loads as you reach it
class Solution:
def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:
a, b = m, n
for i, j in ops:
a = min(a, i)
b = min(b, j)
return a * b