Mathematics

1. Prime Numbers

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Primality Test

A simple way to check if a number n is prime is to test for divisibility by all integers from 2 up to sqrt(n). If none of these divide n evenly, it's prime. This works because if n has a divisor larger than its square root, it must also have a divisor smaller than it.

Time: O(sqrt(n)) | Space: O(1)

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

Sieve of Eratosthenes

When you need to find all primes up to a limit N, the Sieve is much faster. It works by creating a boolean array isPrime up to N, initially all set to true. It then iterates from 2 upwards. If a number p is found to be prime, it marks all multiples of p (starting from p*p) as not prime. We start from p*p because any smaller multiple of p (like 2*p) would have already been marked by a smaller prime (in this case, 2).

Time: O(n log log n) | Space: O(n)

def sieve(N):
    isPrime = [True] * (N + 1)
    if N >= 0: isPrime[0] = False
    if N >= 1: isPrime[1] = False
    for p in range(2, int(N**0.5) + 1):
        if isPrime[p]:
            for (multiple in range(p*p, N + 1, p)):
                isPrime[multiple] = False
    
    primes = []
    for i in range(2, N + 1):
        if isPrime[i]:
            primes.append(i)
    return primes

Classic Problem: Count Primes

Given an integer n, return the number of prime numbers that are strictly less than n. The Sieve of Eratosthenes is the perfect tool for this.

class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 2:
            return 0
        isPrime = [True] * n
        isPrime[0] = isPrime[1] = False
        for i in range(2, int(n**0.5) + 1):
            if isPrime[i]:
                for multiple in range(i*i, n, i):
                    isPrime[multiple] = False
        count = 0
        for i in range(2, n):
            if isPrime[i]:
                count += 1
        return count

2. GCD & LCM

Greatest Common Divisor (GCD): The largest integer that divides two numbers without a remainder.

Euclidean Algorithm

A highly efficient method for computing GCD. The principle is that gcd(a, b) = gcd(b, a % b). The base case is when b becomes 0, at which point a is the GCD.

Time: O(log(min(a,b))) | Space: O(1) (for iterative version)

# Python: Euclidean Algorithm for GCD
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# LCM can be calculated using GCD
def lcm(a, b):
    # To avoid overflow, do division first
    if a == 0 or b == 0:
        return 0
    return abs(a * b) // gcd(a, b)

Classic Problem: GCD of Strings

For two strings s1 and s2, we say s1 divides s2 if and only if s2 = s1 + s1 + ... + s1. Find the largest string x that divides both s1 and s2. A key insight is that if such an x exists, then s1 + str2 must equal s2 + s1. The length of x will be the GCD of the lengths of s1 and s2.

from math import gcd
class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if str1 + str2 != str2 + str1:
            return ""
        gcd_len = gcd(len(str1), len(str2))
        return str1[:gcd_len]

3. Modular Arithmetic

This is a system of arithmetic for integers where numbers "wrap around" after reaching a certain value—the modulus. It's crucial for managing calculations with very large numbers.

Binary Exponentiation (Exponentiation by Squaring)

This technique calculates (base^exp) % mod in O(log exp) time, avoiding overflow issues that would arise from calculating base^exp first.

Time: O(log exp) | Space: O(1)

def power(base, exp, mod):
    res = 1
    base %= mod
    while exp > 0:
        if exp % 2 == 1:
            res = (res * base) % mod
        base = (base * base) % mod
        exp //= 2
    return res

Modular Multiplicative Inverse

The inverse of A modulo M is a number x such that (A * x) % M = 1. This allows for division in modular arithmetic: (B / A) % M becomes (B * x) % M. An inverse only exists if gcd(A, M) = 1.

Fermat's Little Theorem: If M is a prime number, the modular inverse of A can be calculated as A^(M-2) % M. We can use our binary exponentiation function for this.

# Assume power() function from above exists
def modInverse(A, M):
    # Requires M to be a prime number
    return power(A, M - 2, M)

4. Combinatorics

Combinatorics is the mathematics of counting. In competitive programming, this often involves calculating permutations and combinations (nCr) under a modulus.

To calculate nCr % p (where p is a prime), we use the formula n! / ((r!) * (n-r)!). With modular arithmetic, this becomes (n! * modInverse(r!) * modInverse((n-r)!)) % p. This requires pre-calculating factorials and their modular inverses.

# Python: Calculating nCr % p
# Assume p is a prime and we have the modInverse() function
MAXN = 1001
p = 10**9 + 7
fact = [1] * MAXN
invFact = [1] * MAXN

def precompute_factorials():
    for i in range(2, MAXN):
        fact[i] = (fact[i - 1] * i) % p
    invFact[MAXN - 1] = modInverse(fact[MAXN - 1], p)
    for i in range(MAXN - 2, -1, -1):
        invFact[i] = (invFact[i + 1] * (i + 1)) % p

# Call this once at the start
# precompute_factorials()

def nCr_mod_p(n, r):
    if r < 0 or r > n:
        return 0
    numerator = fact[n]
    denominator = (invFact[r] * invFact[n - r]) % p
    return (numerator * denominator) % p

Classic Problem: Unique Paths

A robot is located at the top-left corner of a m x n grid. It can only move down or right. How many possible unique paths are there to the bottom-right corner? This is a classic combinatorics problem. To reach the end, the robot must make a total of (m-1) down moves and (n-1) right moves. The total number of moves is (m-1) + (n-1). The problem is equivalent to choosing which of these total moves will be "down" moves (the rest will be "right").

import math
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # It takes (m-1) down moves and (n-1) right moves.
        # Total moves = (m - 1) + (n - 1).
        # We need to choose which of the total moves are down moves.
        # This is a combination problem: C(total_moves, down_moves).
        return math.comb(m + n - 2, m - 1)