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·
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 Approaches
class Solution:
def countDigits(self, n):
digits = 0
while n:
n, rem = divmod(n, 10)
digits += 1
return digits

Count Commas in Range​

Easy·
class Solution:
def countCommas(self, n: int) -> int:
return max(n - 999, 0)

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

3483. Unique 3-Digit Even Numbers​

Easy·
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 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)

3602. Hexadecimal and Hexatrigesimal Conversion​

Easy·
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·
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·
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 Approaches
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·
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·
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·
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

Power Checks​

326. Power of Three​

Easy·
4 Approaches
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 Approaches
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·
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