Discrete Mathematics for Interviews

Interview Relevance: Discrete math is the backbone of algorithm design. Number theory powers cryptography and hashing, bit manipulation enables O(1) tricks and bitmask DP, and mathematical reasoning lets you prove correctness and compute complexities. Google interviews frequently test these fundamentals directly or embed them within algorithmic problems.

1. Number Theory

GCD and LCM

Greatest Common Divisor (GCD): Largest integer that divides both a and b.

Euclidean Algorithm: Repeatedly replace (a, b) with (b, a mod b) until b = 0.

gcd(48, 18):
  48 = 2 × 18 + 12     gcd(48, 18) = gcd(18, 12)
  18 = 1 × 12 + 6      gcd(18, 12) = gcd(12, 6)
  12 = 2 × 6 + 0       gcd(12, 6)  = 6

Answer: gcd(48, 18) = 6

Why does it work?
  If d divides both a and b, then d divides (a - qb) = a mod b.
  So gcd(a, b) = gcd(b, a mod b).
  Since the remainder shrinks each step, we eventually reach 0.

CPP

// Euclidean algorithm — O(log(min(a, b)))
int gcd(int a, int b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

// Or simply: __gcd(a, b) in C++ (or std::gcd in C++17)

// LCM — divide FIRST to avoid overflow
long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

Time complexity: O(log(min(a, b))) — because after two steps, the larger number is at least halved (Lame's theorem: number of steps <= 5 × number of digits of min(a,b)).

Key properties:

gcd(a, 0) = a
gcd(a, b) = gcd(b, a mod b)
gcd(a, b) = gcd(a - b, b)    for a > b
LCM(a, b) = a × b / gcd(a, b)
gcd(a, b, c) = gcd(gcd(a, b), c)

Extended Euclidean Algorithm

Find integers x, y such that: ax + by = gcd(a, b)

This is fundamental for computing modular inverses.

Extended GCD for a=30, b=20:
  30 = 1×20 + 10     →  10 = 30 - 1×20
  20 = 2×10 + 0      →  gcd = 10

Back-substitute:
  10 = 30×1 + 20×(-1)
  So x=1, y=-1: 30×1 + 20×(-1) = 10 = gcd(30, 20)  ✓

CPP

// Extended GCD: returns gcd, sets x and y such that a*x + b*y = gcd
long long extgcd(long long a, long long b, long long& x, long long& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x1, y1;
    long long g = extgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

Derivation:

gcd(a, b) = gcd(b, a%b)

If b*x₁ + (a%b)*y₁ = gcd   (recursive call gives x₁, y₁)
Then: b*x₁ + (a - ⌊a/b⌋*b)*y₁ = gcd
      a*y₁ + b*(x₁ - ⌊a/b⌋*y₁) = gcd

So: x = y₁,  y = x₁ - ⌊a/b⌋*y₁

Application: Finding modular inverse. If gcd(a, m) = 1, then ax + my = 1, so a*x ≡ 1 (mod m), meaning x is the modular inverse of a mod m.

Linear Diophantine Equations

Problem: Find integer solutions to ax + by = c.

Solutions exist iff gcd(a, b) divides c.

If (x₀, y₀) is one solution, all solutions are:
  x = x₀ + (b/g)*t
  y = y₀ - (a/g)*t
  where g = gcd(a, b), t is any integer

CPP

// Find one solution to ax + by = c, or return false if none exists
bool solveDiophantine(long long a, long long b, long long c,
                      long long& x, long long& y) {
    long long x0, y0;
    long long g = extgcd(abs(a), abs(b), x0, y0);
    if (c % g != 0) return false;

    x = x0 * (c / g);
    y = y0 * (c / g);
    if (a < 0) x = -x;
    if (b < 0) y = -y;
    return true;
}

Modular Arithmetic

Modular arithmetic is essential in competitive programming and cryptography.

(a + b) mod m = ((a mod m) + (b mod m)) mod m
(a × b) mod m = ((a mod m) × (b mod m)) mod m
(a - b) mod m = ((a mod m) - (b mod m) + m) mod m   ← add m to handle negatives

Division is NOT straightforward:
  (a / b) mod m ≠ ((a mod m) / (b mod m)) mod m
  Instead: (a / b) mod m = (a × b⁻¹) mod m
  where b⁻¹ is the modular inverse of b

Common modular arithmetic pitfalls:

CPP

// WRONG: overflow before mod
int result = (a * b) % MOD;  // a*b might overflow int!

// CORRECT: cast to long long
long long result = (1LL * a % MOD * b % MOD) % MOD;

// WRONG: negative result
int result = (a - b) % MOD;  // might be negative in C++!

// CORRECT: add MOD
int result = ((a - b) % MOD + MOD) % MOD;

Modular Exponentiation (Binary Exponentiation)

Compute a^n mod m in O(log n) time.

Key insight: Express n in binary and use repeated squaring.

a^13 where 13 = 1101₂:
  13 = 8 + 4 + 1
  a^13 = a^8 × a^4 × a^1

Step-by-step:
  Start: result=1, base=a

  Bit 0 (=1): result = result × base = a,     base = a²
  Bit 1 (=0): result unchanged,                base = a⁴
  Bit 2 (=1): result = a × a⁴ = a⁵,           base = a⁸
  Bit 3 (=1): result = a⁵ × a⁸ = a¹³          done!

CPP

// O(log exp) — the workhorse of modular arithmetic
long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

Applications:

Computing modular inverse: a^(-1) ≡ a^(p-2) mod p (Fermat's little theorem)
Matrix exponentiation for Fibonacci, linear recurrences
Large exponents in cryptography

Fermat's Little Theorem

If p is prime and gcd(a, p) = 1:

a^(p-1) ≡ 1 (mod p)

Therefore: a^(-1) ≡ a^(p-2) (mod p)

Example: Find 3⁻¹ mod 7.
  3^(7-2) = 3^5 = 243
  243 mod 7 = 243 - 34×7 = 243 - 238 = 5
  Check: 3 × 5 = 15 ≡ 1 (mod 7)  ✓

This is how we compute modular inverses when the modulus is prime!

Chinese Remainder Theorem (CRT)

Given a system of congruences with pairwise coprime moduli:

x ≡ r₁ (mod m₁)
x ≡ r₂ (mod m₂)
...
x ≡ rₖ (mod mₖ)

There exists a unique solution modulo M = m₁ × m₂ × ... × mₖ.

CPP

// CRT: solve system of x ≡ r[i] (mod m[i])
// Returns (solution, product of all moduli)
pair<long long, long long> crt(vector<long long>& r, vector<long long>& m) {
    long long curR = r[0], curM = m[0];

    for (int i = 1; i < r.size(); i++) {
        // Solve: curR + curM*t ≡ r[i] (mod m[i])
        // curM*t ≡ r[i] - curR (mod m[i])
        long long x, y;
        long long g = extgcd(curM, m[i], x, y);
        long long diff = r[i] - curR;

        if (diff % g != 0) return {-1, -1}; // no solution

        long long lcmVal = curM / g * m[i];
        long long t = diff / g % (m[i] / g) * x % (m[i] / g);
        curR = ((curR + curM * t) % lcmVal + lcmVal) % lcmVal;
        curM = lcmVal;
    }

    return {curR, curM};
}

Sieve of Eratosthenes

Find all primes up to n.

Algorithm:
  Mark all numbers 2..n as potentially prime.
  For i = 2, 3, 4, ..., √n:
    If i is prime:
      Mark all multiples of i starting from i² as composite.
      (multiples below i² are already handled by smaller primes)

Visual for n = 30:
  2  3  4̶  5  6̶  7  8̶  9̶  1̶0̶  11  1̶2̶  13  1̶4̶  1̶5̶  1̶6̶  17  1̶8̶  19  2̶0̶  2̶1̶  2̶2̶  23  2̶4̶  2̶5̶  2̶6̶  2̶7̶  2̶8̶  29  3̶0̶

Primes ≤ 30: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

CPP

// Sieve of Eratosthenes — O(n log log n)
vector<bool> sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; (long long)i * i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return is_prime;
}

Time: O(n log log n) — the harmonic series over primes converges very slowly.

Space optimization: Sieve only odd numbers (halves memory), or use bitset.

Linear Sieve — O(n)

Each composite number is marked exactly once (by its smallest prime factor).

CPP

vector<int> linearSieve(int n) {
    vector<int> smallest_prime(n + 1, 0);
    vector<int> primes;

    for (int i = 2; i <= n; i++) {
        if (smallest_prime[i] == 0) {
            smallest_prime[i] = i;
            primes.push_back(i);
        }
        for (int j = 0; j < primes.size() && primes[j] <= smallest_prime[i]
                         && (long long)i * primes[j] <= n; j++) {
            smallest_prime[i * primes[j]] = primes[j];
        }
    }
    return primes;
}

Prime Factorization

CPP

// O(√n) trial division
map<int, int> factorize(int n) {
    map<int, int> factors;
    for (int i = 2; (long long)i * i <= n; i++) {
        while (n % i == 0) {
            factors[i]++;
            n /= i;
        }
    }
    if (n > 1) factors[n]++; // remaining prime factor > √n
    return factors;
}

// O(log n) with precomputed smallest prime factor (from linear sieve)
vector<int> factorizeWithSPF(int n, vector<int>& spf) {
    vector<int> factors;
    while (n > 1) {
        factors.push_back(spf[n]);
        int p = spf[n];
        while (n % p == 0) n /= p;
    }
    return factors;
}

Number of divisors of n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ:

d(n) = (a₁ + 1) × (a₂ + 1) × ... × (aₖ + 1)

Example: 60 = 2² × 3¹ × 5¹
d(60) = (2+1)(1+1)(1+1) = 12
Divisors: 1,2,3,4,5,6,10,12,15,20,30,60

Euler's Totient Function

phi(n) = count of integers in [1, n] that are coprime with n.

If n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ:

phi(n) = n × (1 - 1/p₁) × (1 - 1/p₂) × ... × (1 - 1/pₖ)

Example: phi(12) = 12 × (1 - 1/2) × (1 - 1/3) = 12 × 1/2 × 2/3 = 4
Numbers coprime to 12 in [1,12]: {1, 5, 7, 11} → 4 numbers ✓

Special cases:
  phi(p) = p - 1              (p prime)
  phi(p^k) = p^k - p^(k-1)   (prime power)
  phi(1) = 1

CPP

int eulerTotient(int n) {
    int result = n;
    for (int i = 2; (long long)i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0) n /= i;
            result -= result / i;
        }
    }
    if (n > 1) result -= result / n;
    return result;
}

// Sieve-based: compute phi for all numbers 1..n
vector<int> totientSieve(int n) {
    vector<int> phi(n + 1);
    iota(phi.begin(), phi.end(), 0); // phi[i] = i

    for (int i = 2; i <= n; i++) {
        if (phi[i] == i) { // i is prime
            for (int j = i; j <= n; j += i) {
                phi[j] -= phi[j] / i;
            }
        }
    }
    return phi;
}

Euler's theorem (generalization of Fermat's): If gcd(a, n) = 1, then a^phi(n) ≡ 1 (mod n).

2. Bit Manipulation

Basic Operations

Bit Manipulation Visual

Essential Bit Tricks

CPP

// ═══════════════════════════════════════════════
// Check if kth bit is set
// ═══════════════════════════════════════════════
bool isSet = (n >> k) & 1;
// or: bool isSet = n & (1 << k);

// Example: n=42 (101010), k=3
// 42 >> 3 = 5 (000101), & 1 = 1 → bit 3 is set

// ═══════════════════════════════════════════════
// Set kth bit (turn on)
// ═══════════════════════════════════════════════
n |= (1 << k);

// Example: n=42 (101010), k=0
// 1 << 0 = 1 (000001)
// 42 | 1 = 43 (101011)

// ═══════════════════════════════════════════════
// Clear kth bit (turn off)
// ═══════════════════════════════════════════════
n &= ~(1 << k);

// Example: n=42 (101010), k=3
// 1 << 3 = 8 (001000)
// ~8 = (110111)
// 42 & ~8 = 34 (100010)

// ═══════════════════════════════════════════════
// Toggle kth bit (flip)
// ═══════════════════════════════════════════════
n ^= (1 << k);

// ═══════════════════════════════════════════════
// Check if power of 2
// ═══════════════════════════════════════════════
bool isPow2 = n > 0 && (n & (n - 1)) == 0;

// Why? A power of 2 has exactly one bit set: 1000...0
// n-1 has all lower bits set:                  0111...1
// AND gives 0.
// Example: 8 = 1000, 7 = 0111, 8 & 7 = 0 ✓
//          6 = 0110, 5 = 0101, 6 & 5 = 0100 ≠ 0 ✗

// ═══════════════════════════════════════════════
// Count set bits (popcount)
// ═══════════════════════════════════════════════
int count = __builtin_popcount(n);     // for int
int count = __builtin_popcountll(n);   // for long long

// Manual implementation (Brian Kernighan's algorithm):
int popcount(int n) {
    int count = 0;
    while (n) {
        n &= (n - 1); // remove lowest set bit
        count++;
    }
    return count;
}
// Time: O(number of set bits) — faster than O(log n) for sparse bits

// ═══════════════════════════════════════════════
// Lowest set bit (rightmost 1)
// ═══════════════════════════════════════════════
int lowbit = n & (-n);

// Why? -n = ~n + 1 (two's complement)
// n  = ...1000  (last 1 and trailing 0s)
// -n = ...1000  (flips everything above the lowest 1)
// AND = ...1000  (isolates the lowest 1)

// Example: n=12 (1100), -12=...11110100 (two's complement, lowest bits shown: ...10100)
// 12 & -12 = 4 (0100) = lowest set bit

// ═══════════════════════════════════════════════
// Remove lowest set bit
// ═══════════════════════════════════════════════
n = n & (n - 1);

// Example: n=12 (1100)
// n-1 = 11 (1011)
// 12 & 11 = 8 (1000) — removed the bit at position 2

// ═══════════════════════════════════════════════
// Iterate over all submasks of a given mask
// ═══════════════════════════════════════════════
for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
    // process submask 'sub'
}
// Don't forget to handle sub = 0 (empty subset) separately if needed

// Total iterations over all masks: Σ 2^popcount(mask) = 3^n
// (by the identity: each bit is in 3 states: not in mask, in mask but not sub, in both)

XOR Properties — The Swiss Army Knife

a ^ 0 = a          identity
a ^ a = 0          self-inverse
a ^ b = b ^ a      commutative
(a ^ b) ^ c = a ^ (b ^ c)   associative
a ^ b ^ b = a      cancellation (XOR is its own inverse)

If a ^ b = c, then a = b ^ c, and b = a ^ c.
XOR can be thought of as "addition without carry" in binary.

Application 1: Find Single Number (LC 136)

All elements appear twice except one. Find it.

CPP

// LC 136: Single Number — O(n) time, O(1) space
int singleNumber(vector<int>& nums) {
    int result = 0;
    for (int x : nums) result ^= x;
    return result;
}

// Why? Pairs cancel: a ^ a = 0. All paired elements cancel, leaving the single one.
// [2, 3, 2, 4, 3] → 2^3^2^4^3 = (2^2)^(3^3)^4 = 0^0^4 = 4

Application 2: Find Two Single Numbers (LC 260)

All elements appear twice except two. Find both.

CPP

// LC 260: Single Number III — O(n) time, O(1) space
vector<int> singleNumber(vector<int>& nums) {
    // Step 1: XOR all → get a ^ b (the two singles)
    int xorAll = 0;
    for (int x : nums) xorAll ^= x;

    // Step 2: Find any set bit in xorAll (a and b differ at this bit)
    int diffBit = xorAll & (-xorAll); // lowest set bit

    // Step 3: Split numbers into two groups by this bit
    int group1 = 0, group2 = 0;
    for (int x : nums) {
        if (x & diffBit) group1 ^= x;
        else group2 ^= x;
    }

    return {group1, group2};
}

Application 3: Single Number II (LC 137) — Every element appears 3 times except one

CPP

// LC 137: Single Number II — O(n) time, O(1) space
int singleNumber(vector<int>& nums) {
    // Count bits modulo 3
    int ones = 0, twos = 0;
    for (int x : nums) {
        ones = (ones ^ x) & ~twos;
        twos = (twos ^ x) & ~ones;
    }
    return ones;

    // Alternative: sum each bit position mod 3
    // int result = 0;
    // for (int bit = 0; bit < 32; bit++) {
    //     int sum = 0;
    //     for (int x : nums) sum += (x >> bit) & 1;
    //     result |= (sum % 3) << bit;
    // }
    // return result;
}

Application 4: Swap without temp

CPP

a ^= b;  // a = a ^ b
b ^= a;  // b = b ^ (a ^ b) = a
a ^= b;  // a = (a ^ b) ^ a = b

// Warning: fails if a and b reference the same memory location!

Bitmask DP — Using Bits to Represent Sets

Represent a set of n elements as an n-bit integer. This enables DP over subsets.

For n elements (n ≤ 20):
  Mask 0b10110 represents the set {1, 2, 4}
  (bits 1, 2, 4 are set — 0-indexed)

Operations on sets:
  Union:        mask1 | mask2
  Intersection: mask1 & mask2
  Complement:   ~mask & ((1 << n) - 1)
  Add element:  mask | (1 << i)
  Remove:       mask & ~(1 << i)
  Contains:     mask & (1 << i)
  Size:         __builtin_popcount(mask)
  Is subset:    (sub & mask) == sub
  Empty:        mask == 0

CPP

// Example: Minimum cost to visit all vertices in a weighted graph
// (essentially TSP — covered in NP-Complete chapter)

// Example: Count Hamiltonian paths
int countHamiltonianPaths(vector<vector<int>>& adj) {
    int n = adj.size();
    // dp[mask][i] = number of paths visiting exactly vertices in mask, ending at i
    vector<vector<int>> dp(1 << n, vector<int>(n, 0));

    for (int i = 0; i < n; i++)
        dp[1 << i][i] = 1;

    for (int mask = 1; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            if (!(mask & (1 << u)) || dp[mask][u] == 0) continue;
            for (int v : adj[u]) {
                if (mask & (1 << v)) continue;
                dp[mask | (1 << v)][v] += dp[mask][u];
            }
        }
    }

    int ALL = (1 << n) - 1;
    int total = 0;
    for (int i = 0; i < n; i++) total += dp[ALL][i];
    return total;
}

Bitwise Tricks for Specific Problems

CPP

// Absolute value without branching
int abs_val = (n ^ (n >> 31)) - (n >> 31);

// Min/Max without branching (ONLY works if a-b doesn't overflow)
int min_val = b + ((a - b) & ((a - b) >> 31));
int max_val = a - ((a - b) & ((a - b) >> 31));

// Check if two numbers have opposite signs
bool opposite = (a ^ b) < 0;

// Round up to next power of 2
unsigned nextPow2(unsigned n) {
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n + 1;
}

// Log base 2 (position of highest set bit)
int log2Floor = 31 - __builtin_clz(n); // for n > 0

// Reverse bits (LC 190)
uint32_t reverseBits(uint32_t n) {
    uint32_t result = 0;
    for (int i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);
        n >>= 1;
    }
    return result;
}

3. Mathematical Sequences

Arithmetic Series

a, a+d, a+2d, ..., a+(n-1)d

Sum = n × (first + last) / 2 = n × (2a + (n-1)d) / 2

Special case: Sum of 1 to n = n(n+1)/2

Proof (by Gauss):
  S =  1 +  2 +  3 + ... + n
  S =  n + n-1 + n-2 + ... + 1
  ─────────────────────────────
  2S = (n+1) + (n+1) + ... + (n+1)  [n terms]
  2S = n(n+1)
  S = n(n+1)/2

Sum of first n odd numbers = n²
  1 + 3 + 5 + ... + (2n-1) = n²

Sum of first n even numbers = n(n+1)
  2 + 4 + 6 + ... + 2n = n(n+1)

Sum of Powers

Σ i    = n(n+1)/2
Σ i²   = n(n+1)(2n+1)/6
Σ i³   = [n(n+1)/2]²     ← sum of cubes = square of sum!

Geometric Series

a, ar, ar², ..., ar^(n-1)

Sum = a × (r^n - 1) / (r - 1)    for r ≠ 1

Special case: 1 + 2 + 4 + ... + 2^(n-1) = 2^n - 1

Infinite geometric series (|r| < 1):
Sum = a / (1 - r)

Harmonic Series

H(n) = 1 + 1/2 + 1/3 + ... + 1/n ≈ ln(n) + γ

where γ ≈ 0.5772 (Euler-Mascheroni constant)

This appears EVERYWHERE in algorithm analysis:

1. Sum of n/i for i=1..n = n × H(n) = O(n log n)
   This is why certain algorithms are O(n log n):
   - Each element i has n/i related elements
   - Total work: Σ n/i = n × H(n)

2. Sieve of Eratosthenes:
   n/2 + n/3 + n/5 + n/7 + ... (over primes)
   = n × Σ 1/p ≈ n × ln(ln(n))
   → O(n log log n)

3. Number of divisors:
   Average number of divisors of numbers 1..n ≈ ln(n)
   Σ d(i) for i=1..n ≈ n × ln(n)

Fibonacci Numbers

F(0) = 0, F(1) = 1
F(n) = F(n-1) + F(n-2)

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

Closed form: F(n) = (φ^n - ψ^n) / √5
  where φ = (1 + √5) / 2 ≈ 1.618  (golden ratio)
        ψ = (1 - √5) / 2 ≈ -0.618

Growth: F(n) ≈ φ^n / √5 (exponential growth)

Computing Fibonacci in O(log n) via Matrix Exponentiation

Key identity:
┌F(n+1)┐   ┌1 1┐^n   ┌1┐
│       │ = │   │    × │ │
└ F(n) ┘   └1 0┘      └0┘

So computing F(n) reduces to computing the nth power of a 2×2 matrix,
which can be done in O(log n) via binary exponentiation.

CPP

// Matrix multiplication for 2×2 matrices
typedef vector<vector<long long>> Matrix;

Matrix multiply(Matrix& A, Matrix& B, long long mod) {
    int n = A.size();
    Matrix C(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod;
    return C;
}

Matrix matPow(Matrix A, long long p, long long mod) {
    int n = A.size();
    Matrix result(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++) result[i][i] = 1; // identity

    while (p > 0) {
        if (p & 1) result = multiply(result, A, mod);
        A = multiply(A, A, mod);
        p >>= 1;
    }
    return result;
}

long long fibonacci(long long n, long long mod) {
    if (n <= 1) return n;
    Matrix M = {{1, 1}, {1, 0}};
    Matrix result = matPow(M, n, mod);
    return result[0][1]; // F(n)
}

Fast Doubling — Even Simpler O(log n) for Fibonacci

Identities:
  F(2k)   = F(k) × [2F(k+1) - F(k)]
  F(2k+1) = F(k)² + F(k+1)²

CPP

// Fast doubling — O(log n) time, O(log n) stack space
pair<long long, long long> fib(long long n) {
    if (n == 0) return {0, 1}; // (F(0), F(1))

    auto [a, b] = fib(n / 2); // (F(k), F(k+1))
    long long c = a * (2 * b - a);    // F(2k)
    long long d = a * a + b * b;      // F(2k+1)

    if (n % 2 == 0)
        return {c, d};        // (F(2k), F(2k+1))
    else
        return {d, c + d};    // (F(2k+1), F(2k+2))
}

// Usage: auto [fn, fn1] = fib(n);  // fn = F(n)

Applications of Fibonacci in Algorithms

Fibonacci heaps: amortized O(1) decrease-key
Euclidean algorithm worst case: consecutive Fibonacci numbers require the most steps
Counting: number of binary strings of length n with no consecutive 1s = F(n+2)
Zeckendorf's theorem: every positive integer has a unique representation as a sum of non-consecutive Fibonacci numbers

4. Graph Theory Mathematical Facts

Handshaking Lemma

Sum of all vertex degrees = 2 × |E|

Proof: Each edge contributes 1 to the degree of each endpoint.

Corollary: The number of vertices with odd degree is always EVEN.

Euler's Formula for Planar Graphs

V - E + F = 2

where V = vertices, E = edges, F = faces (including outer face)

Example — cube projected onto plane:
  V = 8, E = 12, F = 6
  8 - 12 + 6 = 2  ✓

Corollary for simple planar graphs: E ≤ 3V - 6
  → K₅ (5 vertices, 10 edges) is not planar: 10 > 3×5-6 = 9
  → K₃,₃ (6 vertices, 9 edges) is not planar: 9 > 3×6-6 = 12?
     Actually 9 ≤ 12, so this test is inconclusive for K₃,₃.
     (K₃,₃ is non-planar for other reasons — no triangles, so E ≤ 2V - 4)

Trees — Key Properties

A tree with n nodes has exactly n - 1 edges.

There is exactly one path between any two nodes.

Removing any edge disconnects the tree.

Adding any edge creates exactly one cycle.

A tree is the MINIMUM connected graph on n nodes.
A tree is the MAXIMUM acyclic graph on n nodes.
Both characterizations give n - 1 edges.

Number of labeled trees on n nodes: n^(n-2) (Cayley's formula)
  n=3: 3^1 = 3 labeled trees
  n=4: 4^2 = 16 labeled trees

Complete Graphs

K_n has:
  - n vertices
  - C(n, 2) = n(n-1)/2 edges
  - Every pair of vertices is connected

K₄:
    A ─── B
    │╲   ╱│
    │  ╲╱  │
    │  ╱╲  │
    │╱   ╲│
    C ─── D
  6 edges: AB, AC, AD, BC, BD, CD

Bipartite Graphs

A graph is bipartite iff it has NO odd-length cycles.

Equivalently: vertices can be 2-colored (no adjacent same color).

Maximum edges in bipartite graph K_{a,b}: a × b
  Maximized when a ≈ b ≈ n/2 → n²/4 edges (Turan's theorem for triangles)

5. Pigeonhole Principle

Statement: If n items are placed into m containers with n > m, at least one container has more than one item.

Generalized: If n items go into m containers, at least one container has at least ceil(n/m) items.

Applications in Algorithm Design

1. Finding Duplicate Number (LC 287)

Given array of n+1 integers in range [1, n], find a duplicate. O(1) extra space.

By pigeonhole: n+1 values in n slots → at least one value repeats.

Solution: Treat array as a linked list where arr[i] points to arr[arr[i]].
Since there's a duplicate, there's a cycle. Use Floyd's algorithm!

CPP

// LC 287: Find the Duplicate Number
int findDuplicate(vector<int>& nums) {
    int slow = nums[0], fast = nums[0];

    // Phase 1: Find intersection point in cycle
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);

    // Phase 2: Find cycle entrance
    slow = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }

    return slow;
}

2. Substring repetition: In a string of length n over alphabet of size k, if n > k^m, there must be a repeated substring of length m.

3. Hash collisions: If we hash more than n items into n buckets, at least one bucket has 2+ items. Expected first collision after ~sqrt(n) insertions (birthday paradox).

4. Subset sums: Given n+1 integers from [1, 2n], there exist two whose sum is some specific structure (e.g., two that are consecutive integers).

6. Logic and Proofs

Proof by Contradiction

Strategy: Assume the opposite of what you want to prove, derive a logical impossibility.

Theorem: √2 is irrational.
Proof:
  Assume √2 = p/q in lowest terms (gcd(p,q) = 1).
  Then 2 = p²/q², so p² = 2q².
  p² is even → p is even → p = 2k.
  (2k)² = 2q² → 4k² = 2q² → q² = 2k² → q is even.
  Both p and q are even → gcd(p,q) ≥ 2. Contradiction!
  So √2 is irrational. □

Algorithm application: Prove that a greedy algorithm produces optimal results by assuming a better solution exists and showing it leads to contradiction.

Proof by Induction

Strategy: Prove base case, then prove "if true for n, then true for n+1."

Theorem: Sum of first n natural numbers = n(n+1)/2

Base case (n=1): 1 = 1×2/2 = 1  ✓

Inductive step: Assume true for n=k: 1+2+...+k = k(k+1)/2
  Show true for n=k+1:
  1+2+...+k+(k+1) = k(k+1)/2 + (k+1)
                   = (k+1)(k/2 + 1)
                   = (k+1)(k+2)/2  ✓ □

Strong induction: Assume true for ALL values up to k, prove for k+1. Often easier for algorithms.

Loop Invariants

A property that is:

True before the loop starts (initialization)
True before each iteration (maintenance)
Implies correctness when loop terminates (termination)

Binary Search Invariant:
  "If target exists in the array, it's in arr[lo..hi]"

  Initialization: lo=0, hi=n-1 → covers entire array  ✓
  Maintenance: If arr[mid] < target, target is in arr[mid+1..hi]
               So lo = mid+1 maintains the invariant  ✓
  Termination: When lo > hi, the range is empty
               → target doesn't exist  ✓

Amortized Analysis

Aggregate method: Total cost of n operations / n = amortized cost per operation.

Example: Dynamic array (vector push_back)
  Most push_back: O(1)
  Occasionally: O(n) when array doubles

  After n push_backs, total copies:
  1 + 2 + 4 + 8 + ... + n ≤ 2n

  Amortized cost per push_back: 2n/n = O(1)

Potential method: Define a potential function Φ. Amortized cost = actual cost + ΔΦ.

7. Common Interview Math Problems with Solutions

Power of Two (LC 231)

CPP

bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

Power of Three (LC 326)

CPP

bool isPowerOfThree(int n) {
    // 3^19 = 1162261467 is the largest power of 3 that fits in int
    return n > 0 && 1162261467 % n == 0;
}
// Why? 3^19 is only divisible by powers of 3.

Happy Number (LC 202)

A number is happy if repeatedly summing squares of digits leads to 1.

19 → 1² + 9² = 82 → 8² + 2² = 68 → 6² + 8² = 100 → 1² + 0² + 0² = 1  ✓ Happy!
2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → ...  (cycle!)  ✗ Not happy

CPP

// LC 202: Happy Number — Floyd's cycle detection
bool isHappy(int n) {
    auto getNext = [](int n) {
        int sum = 0;
        while (n) {
            int d = n % 10;
            sum += d * d;
            n /= 10;
        }
        return sum;
    };

    int slow = n, fast = getNext(n);
    while (fast != 1 && slow != fast) {
        slow = getNext(slow);
        fast = getNext(getNext(fast));
    }
    return fast == 1;
}

Excel Sheet Column Number (LC 171)

A → 1, B → 2, ..., Z → 26
AA → 27, AB → 28, ...
This is base-26 encoding (but 1-indexed, not 0-indexed!)

CPP

// LC 171: Excel Sheet Column Number
int titleToNumber(string columnTitle) {
    int result = 0;
    for (char c : columnTitle) {
        result = result * 26 + (c - 'A' + 1);
    }
    return result;
}

// LC 168: Excel Sheet Column Title (reverse)
string convertToTitle(int columnNumber) {
    string result;
    while (columnNumber > 0) {
        columnNumber--; // 1-indexed to 0-indexed
        result = char('A' + columnNumber % 26) + result;
        columnNumber /= 26;
    }
    return result;
}

Integer to Roman (LC 12)

CPP

string intToRoman(int num) {
    vector<pair<int, string>> vals = {
        {1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"},
        {100, "C"},  {90, "XC"},  {50, "L"},  {40, "XL"},
        {10, "X"},   {9, "IX"},   {5, "V"},   {4, "IV"},
        {1, "I"}
    };

    string result;
    for (auto& [val, sym] : vals) {
        while (num >= val) {
            result += sym;
            num -= val;
        }
    }
    return result;
}

Count Primes (LC 204)

CPP

int countPrimes(int n) {
    if (n <= 2) return 0;
    vector<bool> is_prime(n, true);
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; (long long)i * i < n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j < n; j += i)
                is_prime[j] = false;
        }
    }

    return count(is_prime.begin(), is_prime.end(), true);
}

Single Number Variations

CPP

// LC 136: Single Number (all appear 2x except one)
int singleNumber(vector<int>& nums) {
    int result = 0;
    for (int x : nums) result ^= x;
    return result;
}

// LC 137: Single Number II (all appear 3x except one)
int singleNumberII(vector<int>& nums) {
    int ones = 0, twos = 0;
    for (int x : nums) {
        ones = (ones ^ x) & ~twos;
        twos = (twos ^ x) & ~ones;
    }
    return ones;
}

// LC 260: Single Number III (all appear 2x except two)
vector<int> singleNumberIII(vector<int>& nums) {
    int xorAll = 0;
    for (int x : nums) xorAll ^= x;

    int diffBit = xorAll & (-xorAll);
    int a = 0, b = 0;
    for (int x : nums) {
        if (x & diffBit) a ^= x;
        else b ^= x;
    }
    return {a, b};
}