Overview

Mathematical problems often require efficient algorithms to handle arithmetic operations, geometry, and number theory. These algorithms are essential for competitive programming and interview questions.

Common Math Topics and Techniques

1. Greatest Common Divisor (GCD)

  • Finds the largest number that divides two integers.
  • Commonly used to simplify fractions or solve problems involving ratios.

Euclid’s Algorithm

# Iterative Approach
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# Example Usage
print(gcd(56, 98))  # Output: 14

2. Least Common Multiple (LCM)

  • The smallest number that is a multiple of two numbers.
  • Relationship with GCD: lcm(a, b) = abs(a * b) // gcd(a, b)
# LCM Calculation
from math import gcd

def lcm(a, b):
    return abs(a * b) // gcd(a, b)

# Example Usage
print(lcm(15, 20))  # Output: 60

3. Prime Numbers

  • A prime number is greater than 1 and divisible only by 1 and itself.

Sieve of Eratosthenes

  • Efficient algorithm to generate all primes up to a given number.
# Sieve of Eratosthenes
def sieve_of_eratosthenes(n):
    is_prime = [True] * (n + 1)
    p = 2
    while p * p <= n:
        if is_prime[p]:
            for i in range(p * p, n + 1, p):
                is_prime[i] = False
        p += 1
    return [x for x in range(2, n + 1) if is_prime[x]]

# Example Usage
print(sieve_of_eratosthenes(30))  # Output: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

4. Modular Arithmetic

  • Operations performed under a modulus (remainder after division).
  • Useful for problems involving large numbers (e.g., in cryptography).

Modular Exponentiation

  • Computes (base^exponent) % mod efficiently.
# Modular Exponentiation
def mod_exp(base, exponent, mod):
    result = 1
    base = base % mod
    while exponent > 0:
        if exponent % 2 == 1:  # Odd exponent
            result = (result * base) % mod
        exponent = exponent // 2
        base = (base * base) % mod
    return result

# Example Usage
print(mod_exp(2, 10, 1000))  # Output: 24

5. Factors and Divisors

  • A factor of a number divides it without leaving a remainder.

Find All Factors

# Factors of a Number
import math

def factors(n):
    result = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            result.append(i)
            if i != n // i:
                result.append(n // i)
    return sorted(result)

# Example Usage
print(factors(28))  # Output: [1, 2, 4, 7, 14, 28]

6. Fibonacci Numbers

  • A sequence where each number is the sum of the two preceding ones.

Iterative Approach

# Fibonacci Sequence

def fibonacci(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

# Example Usage
print(fibonacci(10))  # Output: 55

7. Geometry

Distance Between Two Points

  • Formula: sqrt((x2 - x1)^2 + (y2 - y1)^2)
# Distance Between Two Points
import math

def distance(x1, y1, x2, y2):
    return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

# Example Usage
print(distance(0, 0, 3, 4))  # Output: 5.0

8. Combinatorics

  • Focuses on counting, arrangement, and combination of objects.

Factorial

# Factorial Calculation

def factorial(n):
    if n == 0 or n == 1:
        return 1
    return n * factorial(n - 1)

# Example Usage
print(factorial(5))  # Output: 120

Binomial Coefficient

  • Formula: C(n, k) = n! / (k! * (n - k)!)
# Binomial Coefficient
from math import factorial

def binomial_coefficient(n, k):
    return factorial(n) // (factorial(k) * factorial(n - k))

# Example Usage
print(binomial_coefficient(5, 2))  # Output: 10

9. Pythagorean Triplets

  • A set of three positive integers a, b, c such that a^2 + b^2 = c^2.
# Generate Pythagorean Triplets

def pythagorean_triplets(limit):
    triplets = []
    for m in range(1, int(math.sqrt(limit)) + 1):
        for n in range(1, m):
            a = m ** 2 - n ** 2
            b = 2 * m * n
            c = m ** 2 + n ** 2
            if c > limit:
                break
            triplets.append((a, b, c))
    return triplets

# Example Usage
print(pythagorean_triplets(30))  # Output: [(3, 4, 5), (5, 12, 13), (7, 24, 25)]

Summary

Mathematical algorithms are foundational for solving complex computational problems efficiently. Mastering these concepts will help tackle a wide variety of algorithmic challenges.