
LeetCode: Math and Geometry
Math and Geometry Intro
What is Math and Geometry
math!
Math and Geometry IRL
math!
Math and Geometry Application: Math and Geometry
Pattern: math!
Ex: bits numbers!!
def math!(n: int) -> int:
return n+19. Palindrome Number ::2:: - Easy
Topics: Math
Intro
Given an integer x, return true if x is a palindrome, and false otherwise. Follow up: Could you solve it without converting the integer to a string?
| Example Input | Output |
|---|---|
| x = 121 | true |
| x = -121 | false |
| x = 10 | false |
Constraints:
-2^31 ≤ x ≤ 2^31 - 1
Abstraction
Determine whether an integer's digits read the same forwards and backwards.
Pseudocode
oh! pseudocode hasn't been written yet, try another card! :)Solution 1: [String] String Reversal - Math/String Two Pointer Compare
def isPalindrome(self, x: int) -> bool:
# String Reversal:
# - Convert integer to string
# tc: O(d), d = number of digits
# sc: O(d) for string and its reversed copy
s = str(x)
# overall: tc O(d) = O(log10 x)
# overall: sc O(d) = O(log10 x)
return s == s[::-1]Solution 2: [Math] Reverse Half of the Number - Math/Digit Manipulation
def isPalindrome(self, x: int) -> bool:
# Reverse Half:
# - Pop digits off the end of x and push them onto rev
# - Stop once rev >= x, meaning we've processed half the digits
# - Compare the remaining front half to the reversed back half
# - Reversing only half avoids overflow in fixed width languages
# Early Exit 1: Single digits
# - Any single digit (0-9) reads the same both ways
if 0 <= x <= 9:
return True
# Early Exit 2: Negative numbers
# - A negative number has a '-' at the front
# but nothing matching it at the end
# - ex: -121 reads backwards as 121-
if x < 0:
return False
# Early Exit 3: Numbers ending in 0
# - For x to be a palindrome, its first digit must equal its last digit
# - If the last digit is 0, the first digit would also have to be 0
# - No integer starts with 0, so it can't be a palindrome
# - ex: 10 reads backwards as 01, which isn't 10
if x % 10 == 0:
return False
# Reversed back half of x
# sc: O(1)
rev = 0
# Move end of list digits until the rev is greater than the original:
# 1221 -> x = 12, rev = 12
# 12321 -> x = 12, rev = 123
# tc: O(d / 2)
while rev < x:
# Read(): grab last digit of x
# - % 10 gives the remainder after dividing by 10,
# which is always the ones digit
# - ex: 1232 % 10 = 2
digit = x % 10
# Shift_rev(): open a slot in the ones place
# - ex: 3 * 10 = 30
rev = rev * 10
# Push(): place new digit into the ones place
# - ex: 30 + 2 = 32
rev = rev + digit
# Pop(): remove the last digit of x
# - // 10 shifts every digit right, dropping the ones digit
# - ex: 1232 // 10 = 123
x //= 10
# Case 1: Even number of digits
# - The loop splits the digits exactly in half
# - x holds the front half, rev holds the back half reversed
# - ex: 1221 -> x = 12, rev = 12
if x == rev:
return True
# Case 2: Odd number of digits
# - Rev will have the larger digit
# - Drop the extra ones place with // 10
# - ex: 12321 -> x = 12, rev = 123
# rev // 10 = 12
if x == rev // 10:
return True
# Neither half matched, not a palindrome
# overall: tc O(d) = O(log10 x), d = number of digits in x
# overall: sc O(1)
return False415. Add Strings ::1:: - Easy
Topics: Math, String, Simulation
Intro
Given two non-negative integers, num1 and num2 represented as string, return the sum of num1 and num2 as a string. You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly.
| Example Input | Output |
|---|---|
| num1 = "11", num2 = "123" | "134" |
| num1 = "456", num2 = "77" | "533" |
| num1 = "0", num2 = "0" | "0" |
Constraints:
1 ≤ num1.length, num2.length ≤ 104
num1 and num2 consist of only digits
num1 and num2 don't have any leading zeros except for the zero itself
Abstraction
Simulate grade school addition digit by digit from right to left, carrying into the next column.
Pseudocode
oh! pseudocode hasn't been written yet, try another card! :)Solution 1: [Two Pointers] Two Pointers From the Right With Carry - Math/String Simulation
def addStrings(self, num1: str, num2: str) -> str:
# Addition:
# - Start at the ones digit (rightmost) of both strings
# - Add the two digits plus any carry from the previous column
# - Write down the ones digit of the total, carry the tens digit
# - Move one column left and repeat
# - Digits are produced right to left, so reverse at the end
# Pointers to the current column in each string
# start at the ones digit (rightmost character)
i = len(num1) - 1
j = len(num2) - 1
# Carry from the previous column (always 0 or 1)
carry = 0
# Result digits, built in reverse order
# sc: O(max(m, n))
res = []
# Keep going while either string has digits left,
# or there's a leftover carry to write
# - ex: "9" + "1" -> both strings run out,
# but carry 1 still needs to become the leading digit
# tc: O(max(m, n))
while 0 <= i or 0 <= j or carry:
# Grab digits from num1 and num2 if they exist
# - ord(c) - ord('0') converts a single digit character to its value
# - ex: ord('7') - ord('0') = 55 - 48 = 7
if i >= 0:
d1 = ord(num1[i]) - ord('0')
else:
d1 = 0
if j >= 0:
d2 = ord(num2[j]) - ord('0')
else:
d2 = 0
# Add the values + carry
total = d1 + d2 + carry
# Grab the ones digit of the total
# - ex: 13 % 10 = 3
res.append(str(total % 10))
# Grab the carry for the next column
# - ex: 13 // 10 = 1
carry = total // 10
# Move one column left in both strings
i -= 1
j -= 1
# Digits were appended ones digit first
# - ex: "533" => ['3', '3', '5']
# Reverse to put the most significant digit first
# - ex: ['3', '3', '5'] => "533"
# tc: O(max(m, n))
res.reverse()
# overall: tc O(max(m, n)), m = len(num1), n = len(num2)
# overall: sc O(max(m, n)) for result digits
return "".join(res)2169. Count Operations to Obtain Zero ::2:: - Easy
Topics: Math, Simulation
Intro
You are given two non-negative integers num1 and num2. In one operation, if num1 >= num2, you must subtract num2 from num1, otherwise subtract num1 from num2. Return the number of operations required to make either num1 = 0 or num2 = 0.
| Example Input | Output |
|---|---|
| num1 = 2, num2 = 3 | 3 |
| num1 = 10, num2 = 10 | 1 |
Constraints:
0 ≤ num1, num2 ≤ 10^5
Abstraction
Repeatedly subtract the smaller number from the larger until one reaches 0, counting the subtractions.
Pseudocode
oh! pseudocode hasn't been written yet, try another card! :)Solution 1: [Simulation] Direct Subtraction Simulation - Math/Simulation
def countOperations(self, num1: int, num2: int) -> int:
# Direct Simulation:
# - Follow the rules exactly, one subtraction per loop
# - Stop as soon as either number reaches 0
# Number of operations performed
ops = 0
# Keep going while neither number is 0
# tc: O(max(num1, num2)) worst case
# - ex: num1 = 100000, num2 = 1 -> 100000 iterations
while num1 and num2:
# num1 is larger (or equal), subtract num2 from it
if num1 >= num2:
num1 -= num2
# num2 is larger, subtract num1 from it
else:
num2 -= num1
# Count this operation
ops += 1
# overall: tc O(max(num1, num2))
# overall: sc O(1)
return opsSolution 2: [Math] Batched Subtraction With Division (Euclidean Algorithm) - Math/GCD
def countOperations(self, num1: int, num2: int) -> int:
# Batched Subtraction:
# - When num1 >= num2, we keep subtracting num2 from num1
# until num1 drops below num2
# - The number of subtractions is num1 // num2
# - What's left of num1 is num1 % num2
# - Instead of doing individual subtractions, we batch them together
# - This is the same Euclidean algorithm for GCD
# Number of operations performed
ops = 0
# Keep going while neither number is 0
# tc: O(log(min(num1, num2))), same as Euclidean GCD
while num1 and num2:
# num1 is larger (or equal)
if num1 >= num2:
# Count how many times num2 fits into num1
# - // gives number of copies of num2 fit into num1
# - ex: num1 = 10, num2 = 3 -> 10 // 3 = 3 subtractions
ops += num1 // num2
# What remains of num1 after those subtractions
# - % gives whats left after those 3 subtractions
# - so % is the same as => num1 - (num1 // num2) * num2
# - ex: 10 % 3 = 1
num1 %= num2
# num2 is larger
else:
ops += num2 // num1
num2 %= num1
# overall: tc O(log(min(num1, num2)))
# overall: sc O(1)
return ops202. Happy Number ::1:: - Easy
Topics: Hash Table, Math, Two Pointers
Intro
Write an algorithm to determine if a number n is happy. A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits. Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy. Return true if n is a happy number, and false if not.
| Example Input | Output |
|---|---|
| n = 19 | true |
| n = 2 | false |
Constraints:
1 ≤ n ≤ 231 - 1
Abstraction
Given a number and constraints, determine if number fits constraints.
Pseudocode
oh! pseudocode hasn't been written yet, try another card! :)Solution 1: Hash Set Detection - Math and Geometry/Math and Geometry
def isHappy(self, n: int) -> bool:
# Note:
# 1. Compute sum of squares of digits repeatedly
# 2. Keep track of numbers seen in a hash set
# 3. If we see a number again, a cycle exists → not happy
# 4. If we reach 1, number is happy
# Result -> Determine if number is happy
# store numbers to detect cycles
seen = set()
# cycle formula
def next_number(num):
return sum(int(d) ** 2 for d in str(num))
while n != 1:
# cycle detected
if n in seen:
return False
seen.add(n)
# compute sum of squares of digits
n = next_number(n)
# reached 1 = happy number
res = True
# overall: time complexity O(log n) (per iteration * number of unique sums)
# overall: space complexity O(log n) (for hash set)
return resSolution 2: Slow Fast Pointer - Math and Geometry/Math and Geometry
def isHappy(self, n: int) -> bool:
# Note:
# Treat sum-of-squares transformation as a linked list
# 2. Slow and fast pointers to detect cycle
# 3. If fast or fast.next reaches 1 -> happy
# 4. If slow == fast → cycle exists -> not happy
# Result -> Determine if number is happy
# cycle formula
def next_number(num):
return sum(int(d) ** 2 for d in str(num))
# set pointers
slow = n
fast = next_number(n)
# slow and fast pointer to check happy number requirements
while fast != 1 and slow != fast:
slow = next_number(slow)
fast = next_number(next_number(fast))
# happy number == 1
res = fast == 1
# overall: time complexity O(log n) (per iteration * number of iterations before cycle)
# overall: space complexity O(1)
return res66. Plus One ::1:: - Easy
Topics: Array, Math
Intro
You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's. Increment the large integer by one and return the resulting array of digits.
| Example Input | Output |
|---|---|
| digits = [1,2,3] | [1,2,4] |
| digits = [4,3,2,1] | [4,3,2,2] |
| digits = [9] | [1,0] |
Constraints:
1 ≤ digits.length ≤ 100
0 ≤ digits[i] ≤ 9
digits does not contain any leading 0's.
Abstraction
Given a number represented as an array of digits (most significant digit first), increment the number by 1 and return the resulting array of digits.
Pseudocode
oh! pseudocode hasn't been written yet, try another card! :)Solution 1: Hash Set Detection - Math and Geometry/Math and Geometry
def plusOne(self, digits: List[int]) -> List[int]:
# Note:
# Process digits from least significant to most significant
# 1. Iterate right to left in array
# 2. Add 1 to the last digit
# 3. Propagate carry if sum >= 10
# 4. If carry remains after the most significant digit, insert at front
# 5. Time complexity O(n), space O(1) extra (besides output)
n = len(digits)
# iterate from last digit to first
for i in range(n - 1, -1, -1):
# add to current digit
digits[i] += 1
# if no carry, finished array, else continue
if digits[i] < 10:
return digits
# if carry, set current to zero, continue
digits[i] = 0
# if carry remains after processing all digits
# prepend [1] to array
res = [1] + digits
# overall: time complexity O(n)
# overall: space complexity O(1)
return res50. Pow(x, n) ::1:: - Medium
Topics: Math, Recursion
Intro
Implement pow(x, n), which calculates x raised to the power n (i.e., xn).
| Example Input | Output |
|---|---|
| x = 2.00000, n = 10 | 1024.00000 |
| x = 2.10000, n = 3 | 9.26100 |
| x = 2.00000, n = -2 | 0.25000 |
Constraints:
-100.0 < x < 100.0
-231 ≤ n ≤ 231 - 1
n is an integer.
Either x is not zero or n > 0.
-104 ≤ xn ≤ 104
Abstraction
Implement pow(x, n).
Pseudocode
oh! pseudocode hasn't been written yet, try another card! :)Solution 1: Recursive Fast Exponentiation - Math and Geometry/Math and Geometry
def myPow(self, x: float, n: int) -> float:
# Note:
# Math behind Fast Exponentiation:
# x^n -> even -> [x^(n/2)]^2
# -> odd -> x * (x^[(n-1)/2])^2
# Example:
# x^6 = (x^3)^2
# x^7 = x * (x^3)^2
# Now simply apply some recursion
# Note:
# 1. Recursively compute half power to reduce computation
# 2. If exponent is negative, use reciprocal: x^-n = 1 / x^n
# 3. Base case: n == 0 → return 1
# Result -> pow() calculation
if n == 0:
return 1.0
if n < 0:
return 1 / self.myPow(x, -n)
half = self.myPow(x, n // 2)
if n % 2 == 0:
return half * half
else:
return half * half * x
# overall: time complexity O(log n)
# overall: space complexity O(log n) due to recursion stackSolution 2: Iterative Fast Binary Exponentiation - Math and Geometry/Math and Geometry
def myPow(self, x: float, n: int) -> float:
# Note:
# Binary Exponentiation uses the binary representation of n
# n = 13 -> 1101
# Start with result = 1 and current_product = x.
# Then for each bit from LSB to MSB:
# If bit is 1 → multiply result by current_product
# Square current_product each step
# Shift to next bit
# Note:
# 1. Use binary exponentiation iteratively
# 2. Convert negative exponent to positive and invert at end
# 3. Multiply result by x whenever the current bit of n is 1
# 4. Shift exponent right each iteration
N = n
if N < 0:
x = 1 / x
N = -N
result = 1.0
current_product = x
while N > 0:
if N % 2 == 1: # current bit is 1
result *= current_product
current_product *= current_product # square for next bit
N //= 2
# overall: time complexity O(log n)
# overall: space complexity O(1)
return result43. Multiply Strings ::2:: - Medium
Topics: Math, Recursion
Intro
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string. Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.
| Example Input | Output |
|---|---|
| num1 = "2", num2 = "3" | "6" |
| num1 = "123", num2 = "456" | "56088" |
Constraints:
1 ≤ num1.length, num2.length ≤ 200
num1 and num2 consist of digits only.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.
Abstraction
Given two numbers represented as strings, return the product of the two numbers.
Pseudocode
oh! pseudocode hasn't been written yet, try another card! :)Solution 1: Simulate Grade School Multiplication - Math and Geometry/Math and Geometry
def multiply(self, num1: str, num2: str) -> str:
# Note:
# 1. Multiply each digit of num1 by each digit of num2
# 2. Store intermediate sums in an array of length len(num1) + len(num2)
# 3. Handle carry for each position
# 4. Convert array to string, skipping leading zeros
# Zero Check
if num1 == "0" or num2 == "0":
return "0"
m, n = len(num1), len(num2)
# max number of digits the product can have when multiplying two integers
pos = [0] * (m + n)
# multiply digits from right to left
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
# i -> index of digit in num1
# j -> index of digit in num2
# single digit multiplication
mul = int(num1[i]) * int(num2[j])
# stores the carry that will affect the next higher digit
p1 = i + j
# stores the ones place for this multiplication
p2 = i + j + 1
# pos[p2] holds previous carry that contributes to new multiplication
total = mul + pos[p2]
# new current digit
pos[p2] = total % 10
# new carry
pos[p1] += total // 10
# convert to string, skipping leading zeros
result = []
# to skip leading zeros in final result
for p in pos:
# if result == empty, ensures we haven't added any non-zero digits yet
# which ensures we only skip leading zeros, not inner zeros
if not result and p == 0:
continue
# append inner zeros or values
result.append(str(p))
# more efficient of concatenating strings
res = "".join(result)
# overall: time complexity O(m*n)
# overall: space complexity O(m+n)
return res2013. Detect Squares ::1:: - Medium
Topics: Array, Hash Table, Design, Counting
Intro
You are given a stream of points on the X-Y plane.
Design an algorithm that: Adds new points from the stream into a data structure. Duplicate points are allowed and should be treated as different points. Given a query point, counts the number of ways such that the three points and the query point form an axis-aligned square with positive area. An axis-aligned square is a square whose edges are all the same length and are either parallel or perpendicular to the x-axis and y-axis. Implement the DetectSquares class: DetectSquares() Initializes the object with an empty data structure. void add(int[] point) Adds a new point point = [x, y] to the data structure. int count(int[] point) Counts the number of ways to form axis-aligned squares with point point = [x, y] as described above.
| Example Input | Output |
|---|---|
| too long | [null, null, null, null, 1, 0, null, 2] |
Constraints:
point.length == 2
0 ≤ x, y, ≤ 1000
At most 3000 calls in total will be made to add and count.
Abstraction
Design a data structure to store points on a 2D grid and count the number of axis-aligned squares that can be formed with a given query point. Points can be added multiple times. Squares must have edges parallel to axes and positive area. Efficiently handle up to 3000 add and count calls.
Pseudocode
oh! pseudocode hasn't been written yet, try another card! :)Solution 1: Hash Map Counting - Math and Geometry/Math and Geometry
class DetectSquares:
def __init__(self):
# Note:
# counts[x][y] -> tracks how many times point (x,y) has been added
# This allows O(1) insertion and O(k) count queries
self.counts = defaultdict(lambda: defaultdict(int))
def add(self, point: List[int]) -> None:
# Increment point count
x_col, y_row = point
self.counts[x_col][y_row] += 1
def count(self, point: List[int]) -> int:
x_col, y_row = point
total = 0
# Look for all points in same column x, but with different y
for curr_y_row, count_at_point in self.counts[x_col].items():
if curr_y_row == y_row: # skip the query point itself
continue
# distance = side length
d = curr_y_row - y_row
# Left square
left_x = x_col - d
count_left_top = self.counts.get(left_x, {}).get(y_row, 0)
count_left_bottom = self.counts.get(left_x, {}).get(curr_y_row, 0)
total += count_at_point * count_left_top * count_left_bottom
# Right square
right_x = x_col + d
count_right_top = self.counts.get(right_x, {}).get(y_row, 0)
count_right_bottom = self.counts.get(right_x, {}).get(curr_y_row, 0)
total += count_at_point * count_right_top * count_right_bottom
return total
# overall: add O(1), count O(k) where k = # points sharing same x
# overall: space complexity O(n) for n points stored