Command Palette

Search for a command to run...

Hectal

Module 39

Math for Coding Interviews

GCD and LCM, primes with a sieve, modular arithmetic, fast exponentiation, modular inverses, nCr, and safe digit manipulation.

Advanced 3 lessons 9 problems ~40 min of lessons
Number Theory and Combinatorics

A handful of number-theory tools appear again and again: Euclid's GCD, the sieve of Eratosthenes, "return the answer modulo 10⁹ + 7", raising numbers to huge powers, dividing under a modulus, and counting arrangements with factorials.

This module explains each tool from first principles, shows the overflow traps in Java, and practises them on problems where the math replaces a loop or makes an impossible count possible.

Best after: Big-O and Complexity

Where this shows up in real systems

Part 1

Learn the ideas

  1. 39.1GCD, LCM and the Sievegcd(a, b) = gcd(b, a mod b) runs in O(log min(a, b)). lcm = a / gcd × b. The sieve marks multiples of each prime to find all primes below n in O(n log log n).14 min
  2. 39.2Modular Arithmetic, Fast Power and nCrReduce after every + and ×. Exponentiate by squaring in O(log e). Divide by multiplying with the modular inverse a^(p − 2) when p is prime.16 min
  3. 39.3Digits, Bases and OverflowExtract digits with % 10 and / 10, convert between bases by repeated division, and check for overflow before it happens.10 min

Part 2

Solve the problems

Work through them in order. Each one shows the pattern it teaches.

  1. 39.1Greatest Common Divisor of StringsEasyNumber Theory and Combinatorics

    GCD applied to string lengths, after a commutativity check.

  2. 39.2Count PrimesMediumNumber Theory and Combinatorics

    The sieve of Eratosthenes.

  3. 39.3Water and Jug ProblemMediumNumber Theory and Combinatorics

    Bézout's identity: reachable amounts are multiples of gcd(x, y) up to x + y.

  4. 39.4Excel Sheet Column NumberEasyNumber Theory and Combinatorics

    Base 26 with digits 1–26.

  5. 39.5Factorial Trailing ZeroesMediumNumber Theory and Combinatorics

    Count factors of 5 instead of computing n!.

  6. 39.6Reverse IntegerMediumNumber Theory and Combinatorics

    Digit extraction with an overflow check before each step.

  7. 39.7Count Good NumbersMediumNumber Theory and Combinatorics

    Fast modular exponentiation for counts with huge n.

  8. 39.8Super PowMediumNumber Theory and Combinatorics

    An exponent given as a digit array: a^(10k + d) = (a^k)^10 × a^d.

  9. 39.9Count AnagramsHardNumber Theory and Combinatorics

    Multinomial coefficients under a modulus with factorials and inverse factorials.