19 — Math & Number Theory

GCD & LCM

function gcd(a: number, b: number): number {
  while (b) { [a, b] = [b, a % b]; }
  return a;
}

function lcm(a: number, b: number): number {
  return (a / gcd(a, b)) * b; // Divide first to avoid overflow
}

// Extended GCD: find x, y such that ax + by = gcd(a,b)
function extGcd(a: number, b: number): [number, number, number] {
  if (b === 0) return [a, 1, 0];
  const [g, x1, y1] = extGcd(b, a % b);
  return [g, y1, x1 - Math.floor(a / b) * y1];
}

---

Prime Numbers

Sieve of Eratosthenes

function sieve(n: number): boolean[] {
  const isPrime = new Array(n + 1).fill(true);
  isPrime[0] = isPrime[1] = false;
  
  for (let i = 2; i * i <= n; i++) {
    if (isPrime[i]) {
      for (let j = i * i; j <= n; j += i) {
        isPrime[j] = false;
      }
    }
  }
  return isPrime;
}
// Time: O(n log log n), Space: O(n)

Primality Test

function isPrime(n: number): boolean {
  if (n < 2) return false;
  if (n < 4) return true;
  if (n % 2 === 0 || n % 3 === 0) return false;
  for (let i = 5; i * i <= n; i += 6) {
    if (n % i === 0 || n % (i + 2) === 0) return false;
  }
  return true;
}
// Time: O(√n)

Prime Factorization

function primeFactors(n: number): Map<number, number> {
  const factors = new Map<number, number>();
  for (let d = 2; d * d <= n; d++) {
    while (n % d === 0) {
      factors.set(d, (factors.get(d) ?? 0) + 1);
      n /= d;
    }
  }
  if (n > 1) factors.set(n, 1);
  return factors;
}

---

Modular Arithmetic

(a + b) % m = ((a % m) + (b % m)) % m
(a * b) % m = ((a % m) * (b % m)) % m
(a - b) % m = ((a % m) - (b % m) + m) % m   // +m to avoid negative
(a / b) % m = (a * modInverse(b, m)) % m     // Use modular inverse

Modular Inverse

// Fermat's little theorem: a^(-1) ≡ a^(p-2) (mod p), p is prime
function modInverse(a: number, mod: number): number {
  return modPow(a, mod - 2, mod);
}

---

Fast Exponentiation

function modPow(base: number, exp: number, mod: number): number {
  let result = 1;
  base %= mod;
  
  while (exp > 0) {
    if (exp & 1) result = (result * base) % mod;
    exp >>= 1;
    base = (base * base) % mod;
  }
  return result;
}
// Time: O(log n)

---

Combinatorics

// nCr mod p (with precomputed factorials)
const MOD = 1e9 + 7;

function precompute(n: number): { fact: number[]; inv: number[] } {
  const fact = new Array(n + 1);
  const inv = new Array(n + 1);
  fact[0] = 1;
  for (let i = 1; i <= n; i++) fact[i] = (fact[i - 1] * i) % MOD;
  inv[n] = modPow(fact[n], MOD - 2, MOD);
  for (let i = n - 1; i >= 0; i--) inv[i] = (inv[i + 1] * (i + 1)) % MOD;
  return { fact, inv };
}

function nCr(n: number, r: number, fact: number[], inv: number[]): number {
  if (r < 0 || r > n) return 0;
  return (fact[n] * inv[r] % MOD) * inv[n - r] % MOD;
}

---

Common Interview Problems

Count Primes

function countPrimes(n: number): number {
  const isPrime = sieve(n - 1);
  return isPrime.filter(Boolean).length;
}

Power of Three

const isPowerOfThree = (n: number) => n > 0 && 1162261467 % n === 0;
// 3^19 = 1162261467 is largest power of 3 in 32-bit int

Happy Number

function isHappy(n: number): boolean {
  const seen = new Set<number>();
  while (n !== 1 && !seen.has(n)) {
    seen.add(n);
    n = String(n).split('').reduce((sum, d) => sum + (+d) ** 2, 0);
  }
  return n === 1;
}

---

Key Takeaways

• GCD: Euclidean algorithm O(log min(a,b)); LCM = a/gcd × b
• Sieve: O(n log log n) to find all primes up to n
• Modular arithmetic: always mod after each operation to prevent overflow
• Fast exponentiation: O(log n) — essential for large powers with mod
• nCr mod p: precompute factorials + modular inverse