08. Math

Math problems on platforms like LeetCode often require a combination of mathematical insight, algorithmic thinking, and coding skills. These problems can range from simple arithmetic operations to complex mathematical theories. Here, I will explain some common types of math problems and the techniques used to solve them.

Common Types of Math Problems and Techniques

528. Random Pick with Weight
529. Basic Calculator II
530. Pow(x, n)
531. K Closest Points to Origin
532. Continuous Subarray Sum
533. Random Pick Index
534. Maximum Swap
535. Add Strings

528. Random Pick with Weight

Problem: Given an array w of positive integers where w[i] describes the weight of index i, write a function pickIndex which randomly picks an index in proportion to its weight.

Approach:

• Use prefix sums and binary search.
• Compute the prefix sum array and use binary search to pick an index based on a random number.

Code:

import random
import bisect

class Solution:
    def __init__(self, w):
        self.prefix_sums = []
        prefix_sum = 0
        for weight in w:
            prefix_sum += weight
            self.prefix_sums.append(prefix_sum)
        self.total_sum = prefix_sum

    def pickIndex(self):
        target = random.randint(1, self.total_sum)
        return bisect.bisect_left(self.prefix_sums, target)

# Example usage:
weights = [1, 3, 2]
obj = Solution(weights)
print(obj.pickIndex())  # Randomly returns 0, 1, or 2 based on weights

Explanation:

1. Prefix Sums: Compute the prefix sum of weights.
2. Binary Search: Use binary search to find the index corresponding to a random target within the total weight range.

227. Basic Calculator II

Problem: Implement a basic calculator to evaluate a simple expression string containing non-negative integers, +, -, *, and / operators.

Approach:

• Use a stack to manage the numbers and operators.
• Traverse the string and handle operations based on operator precedence.

Code:

def calculate(s):
    if not s:
        return 0

    stack = []
    num = 0
    sign = '+'
    s += '+'

    for c in s:
        if c.isdigit():
            num = num * 10 + int(c)
        elif c in '+-*/':
            if sign == '+':
                stack.append(num)
            elif sign == '-':
                stack.append(-num)
            elif sign == '*':
                stack.append(stack.pop() * num)
            elif sign == '/':
                stack.append(int(stack.pop() / num))
            sign = c
            num = 0

    return sum(stack)

# Example usage:
expression = "3+2*2"
print(calculate(expression))  # Output: 7

Explanation:

1. Stack for Numbers: Use a stack to handle numbers and intermediate results.
2. Operator Precedence: Handle * and / immediately, defer + and - until the end.

50. Pow(x, n)

Problem: Implement pow(x, n), which calculates x raised to the power n.

Approach:

• Use recursion and the concept of exponentiation by squaring.

Code:

def my_pow(x, n):
    def helper(x, n):
        if n == 0:
            return 1
        half = helper(x, n // 2)
        if n % 2 == 0:
            return half * half
        else:
            return half * half * x

    if n < 0:
        x = 1 / x
        n = -n
    return helper(x, n)

# Example usage:
x = 2.0
n = 10
print(my_pow(x, n))  # Output: 1024.0

Explanation:

1. Recursion: Break down the problem into smaller subproblems using recursion.
2. Exponentiation by Squaring: Efficiently compute powers by squaring intermediate results.

973. K Closest Points to Origin

Problem: Given an array of points where points[i] = [xi, yi] represents a point on the XY plane, return the k closest points to the origin (0, 0).

Approach:

• Use a max-heap to keep track of the k closest points.

Code:

import heapq

def k_closest(points, k):
    max_heap = []
    for x, y in points:
        dist = -(x**2 + y**2)
        if len(max_heap) == k:
            heapq.heappushpop(max_heap, (dist, x, y))
        else:
            heapq.heappush(max_heap, (dist, x, y))
    return [(x, y) for (dist, x, y) in max_heap]

# Example usage:
points = [[1, 3], [-2, 2]]
k = 1
print(k_closest(points, k))  # Output: [[-2, 2]]

Explanation:

1. Max-Heap: Use a max-heap to keep the closest k points by distance.
2. Distance Calculation: Calculate the Euclidean distance and maintain the closest points.

523. Continuous Subarray Sum

Problem: Given an integer array nums and an integer k, return true if nums has a continuous subarray of size at least two whose elements sum up to a multiple of k.

Approach:

• Use a hash map to store the running sum modulo k.

Code:

def check_subarray_sum(nums, k):
    sum_map = {0: -1}
    running_sum = 0

    for i, num in enumerate(nums):
        running_sum += num
        if k != 0:
            running_sum %= k
        if running_sum in sum_map:
            if i - sum_map[running_sum] > 1:
                return True
        else:
            sum_map[running_sum] = i

    return False

# Example usage:
nums = [23, 2, 4, 6, 7]
k = 6
print(check_subarray_sum(nums, k))  # Output: True

Explanation:

1. Running Sum: Calculate the running sum modulo k.
2. Hash Map: Use a hash map to track the first occurrence of each remainder and check the distance between occurrences.

398. Random Pick Index

Problem: Given an integer array nums with possible duplicates, implement the Solution class:

• pick(target): Randomly returns the index of the target number.

Approach:

• Use reservoir sampling to handle random selection efficiently.

Code:

import random

class Solution:
    def __init__(self, nums):
        self.nums = nums

    def pick(self, target):
        count = 0
        result = -1
        for i, num in enumerate(self.nums):
            if num == target:
                count += 1
                if random.randint(1, count) == count:
                    result = i
        return result

# Example usage:
nums = [1, 2, 3, 3, 3]
target = 3
obj = Solution(nums)
print(obj.pick(target))  # Randomly returns one of the indices: 2, 3, or 4

Explanation:

1. Reservoir Sampling: Ensure each index has an equal probability of being chosen.
2. Count Occurrences: Traverse the array, counting occurrences of the target and selecting based on random chance.

670. Maximum Swap

Problem: Given a non-negative integer, you can swap two digits at most once to get the maximum valued number. Return the maximum valued number.

Approach:

• Use a greedy algorithm to find the best swap.

Code:

def maximum_swap(num):
    digits = list(str(num))
    last = {int(x): i for i, x in enumerate(digits)}

    for i, x in enumerate(digits):
        for d in range(9, int(x), -1):
            if last.get(d, -1) > i:
                digits[i], digits[last[d]] = digits[last[d]], digits[i]
                return int(''.join(digits))

    return num

# Example usage:
num = 2736
print(maximum_swap(num))  # Output: 7236

Explanation:

1. Greedy Approach: Find the highest digit that can be swapped to maximize the number.
2. Track Last Occurrence: Use a dictionary to store the last occurrence of each digit for efficient swaps.

415. Add Strings

Problem: Given two non-negative integers represented as strings, return the sum of the two numbers as a string.

Approach:

• Use digit-by-digit addition with carry handling.

Code:

def add_strings(num1, num2):
    i, j = len(num1) - 1, len(num2) - 1
    carry = 0
    result = []

    while i >= 0 or j >= 0 or carry:
        x = int(num1[i]) if i >= 0 else 0
        y = int(num2[j]) if j >= 0 else 0
        total = x + y + carry
        carry = total // 10
        result.append(total % 10)
        i -= 1
        j -= 1

    return ''.join(map(str, result[::-1]))

# Example usage:
num1 = "123"
num2 = "456"