Jc-alt logo
jc
LeetCode: Math and Geometry

LeetCode: Math and Geometry

··
20 min read
·data structures and algorithms

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+1

9. 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 InputOutput
x = 121true
x = -121false
x = 10false

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 False

415. 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 InputOutput
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 InputOutput
num1 = 2, num2 = 33
num1 = 10, num2 = 101

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 ops

Solution 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 ops

202. 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 InputOutput
n = 19true
n = 2false

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 res

Solution 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 res

66. 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 InputOutput
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 res

50. 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 InputOutput
x = 2.00000, n = 101024.00000
x = 2.10000, n = 39.26100
x = 2.00000, n = -20.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 stack

Solution 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 result

43. 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 InputOutput
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 res

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