Math Algorithms: Code Templates in 6 Languages

Coding Patterns - Guide to 30 Core Algorithm Patterns

Math Algorithms: Complete Guide with Worked Examples

If you have not read the concept guide , start there for the intuition and the complexity analysis. This page holds the three primitives worth memorizing for interview math. They are the Euclidean GCD, fast modular exponentiation, and the Sieve of Eratosthenes. The first two run in

O(log N)

time with

O(1)

space. The sieve trades

O(N)

memory for near-instant prime checks afterward.

Main Template: Euclidean GCD

The Euclidean algorithm finds the greatest common divisor by replacing the larger of two numbers with the remainder of dividing it by the smaller one. The loop ends when the remainder is zero, and the last nonzero divisor is the answer.

Use this for Water and Jug Problem .

function gcd(a, b) {
    while (b !== 0) {
        // The remainder is always smaller than b, so each
        // step shrinks the pair toward the case b == 0
        [a, b] = [b, a % b];
    }
    return a;
}

int gcd(int a, int b) {
    while (b != 0) {
        // Hold one value during the swap. The remainder
        // a % b always lands below the current b.
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int gcd(int a, int b) {
    while (b != 0) {
        // Each pass replaces the pair with (b, a % b),
        // shrinking it toward the base case b == 0
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

Templates only help if you can recall them without staring at the screen. Turn these snippets into flashcards for daily mobile review.

Code Breakdown

Key Variables

a, b: the working pair. After each step, a holds the previous divisor and b holds the new remainder.
temp: only needed in languages without parallel assignment (Java, C++). It holds one value during the swap.

Visual Mechanism

    stateDiagram-v2
    [*] --> Loop: a, b
    Loop --> Swap: b != 0
    Swap --> Loop: replace with (b, a mod b)
    Loop --> Done: b == 0
    Done --> [*]: return a

Critical Sections

The termination condition is the whole trick. When b reaches zero, a divides both original inputs exactly, so it is the GCD. The loop is fast because a remainder is always smaller than the divisor that produced it, so the pair shrinks on every iteration. That is the difference between this loop and a scan over every possible divisor.

The swap is the only data movement. Parallel assignment in Python, JavaScript, Go, and Ruby makes it a single line. Java and C++ need the temporary variable because the assignment happens one operand at a time.

If you need the least common multiple, derive it from the GCD. LCM(a, b) = a / GCD(a, b) * b. Divide before multiplying so the intermediate value stays small.

Variations

1. Fast Exponentiation (Modular)

Use this when the exponent can be huge, or when results must stay bounded. Squaring the base and halving the exponent cuts the work from N multiplications to about log2(N). Apply the modulus after every multiply so the values stay small in fixed-width languages.

Use this for Pow(x, n) and Super Pow .

Time

O(log N)

| Space

O(1)

function modPow(base, exponent, modulus) {
    if (modulus === 1) return 0;

    let result = 1;
    base = base % modulus;

    while (exponent > 0) {
        // When the lowest bit of the exponent is set,
        // the current power belongs in the result
        if (exponent % 2 === 1) {
            result = (result * base) % modulus;
        }
        // Squaring the base handles the next bit of the exponent
        base = (base * base) % modulus;
        exponent = Math.floor(exponent / 2);
    }

    return result;
}

def mod_pow(base: int, exponent: int, modulus: int) -> int:
    if modulus == 1:
        return 0

    result = 1
    base %= modulus
    while exponent > 0:
        # When the lowest bit of the exponent is set,
        # the current power belongs in the result
        if exponent % 2 == 1:
            result = result * base % modulus
        # Squaring the base handles the next bit of the exponent
        base = base * base % modulus
        exponent //= 2
    return result

def mod_pow(base, exponent, modulus)
    return 0 if modulus == 1

    result = 1
    base %= modulus
    while exponent > 0
        result = result * base % modulus if exponent.odd?
        base = base * base % modulus
        exponent /= 2
    end
    result
end

2. Sieve of Eratosthenes

Use this when you need every prime up to a bound, or when one problem asks many prime checks. The sieve marks each composite once per prime factor instead of checking every candidate against every smaller number.

Use this for Count Primes .

Time

O(N log log N)

| Space

O(N)

function sieve(limit) {
    if (limit < 2) return [];

    const isPrime = new Array(limit + 1).fill(true);
    isPrime[0] = isPrime[1] = false;

    for (let i = 2; i * i <= limit; i++) {
        if (isPrime[i]) {
            // Start at i*i: smaller multiples were already
            // marked by a smaller prime factor
            for (let j = i * i; j <= limit; j += i) {
                isPrime[j] = false;
            }
        }
    }

    const primes = [];
    for (let i = 2; i <= limit; i++) {
        if (isPrime[i]) primes.push(i);
    }
    return primes;
}

def sieve(limit: int) -> List[int]:
    if limit < 2:
        return []

    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False

    i = 2
    while i * i <= limit:
        if is_prime[i]:
            # Start at i*i: smaller multiples were already
            # marked by a smaller prime factor
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False
        i += 1

    return [num for num in range(2, limit + 1) if is_prime[num]]

List<Integer> sieve(int limit) {
    if (limit < 2) return new ArrayList<>();

    boolean[] isPrime = new boolean[limit + 1];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i * i <= limit; i++) {
        if (isPrime[i]) {
            // Smaller multiples of i are already marked,
            // so the loop starts at i*i
            for (long j = (long) i * i; j <= limit; j += i) {
                isPrime[(int) j] = false;
            }
        }
    }

    List<Integer> primes = new ArrayList<>();
    for (int i = 2; i <= limit; i++) {
        if (isPrime[i]) primes.add(i);
    }
    return primes;
}

vector<int> sieve(int limit) {
    if (limit < 2) return {};

    vector<bool> is_prime(limit + 1, true);
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i * i <= limit; i++) {
        if (is_prime[i]) {
            // Start at i*i: smaller multiples are
            // already marked by smaller primes
            for (long long j = (long long)i * i; j <= limit; j += i) {
                is_prime[j] = false;
            }
        }
    }

    vector<int> primes;
    for (int i = 2; i <= limit; i++) {
        if (is_prime[i]) primes.push_back(i);
    }
    return primes;
}

func sieve(limit int) []int {
    if limit < 2 {
        return []int{}
    }

    isPrime := make([]bool, limit+1)
    for i := range isPrime {
        isPrime[i] = true
    }
    isPrime[0], isPrime[1] = false, false

    for i := 2; i*i <= limit; i++ {
        if isPrime[i] {
            // Start at i*i: smaller multiples are
            // already marked by smaller primes
            for j := i * i; j <= limit; j += i {
                isPrime[j] = false
            }
        }
    }

    primes := []int{}
    for i := 2; i <= limit; i++ {
        if isPrime[i] {
            primes = append(primes, i)
        }
    }
    return primes
}

def sieve(limit)
    return [] if limit < 2

    is_prime = Array.new(limit + 1, true)
    is_prime[0] = is_prime[1] = false

    i = 2
    while i * i <= limit
        if is_prime[i]
            # Start at i*i: smaller multiples are
            # already marked by smaller primes
            j = i * i
            while j <= limit
                is_prime[j] = false
                j += i
            end
        end
        i += 1
    end

    (2..limit).select { |n| is_prime[n] }
end

Each variation above is a separate review card in the app. Drill them individually so you do not mix up the conditions under pressure.

Now head to the practice problems to apply these templates to real interview questions.

Now that you have the templates, the next step is application. Head to the practice problems or start reviewing these templates with spaced repetition .