SyntaxPilot
Courses/DSA and Coding Problems/Lesson 79
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 79 of 90

Math for coding: GCD, sieve of Eratosthenes, fast power, modular arithmetic

queued

These are the notes for DSA episode 79. Four tools that coding problems use again and again, each invented from a slow program that fails on screen. A sweet shop packs boxes: GCD by counting down is wrong for gcd(0, 5) and times out on two 12-digit numbers, so we invent Euclid's algorithm (gcd(a, b) = gcd(b, a % b)). A teacher counts primes: trial division handles a million but times out at 10⁸, so we flip the question and invent the sieve of Eratosthenes (10⁸ in about a second). The rice on the chessboard gives a number too big for any computer, so we work modulo 1,000,000,007 and invent fast power (2^(10¹⁸) in about 60 steps), which also gives the modular inverse. Then three real bugs: an int overflow that becomes a negative array index, a forgotten % MOD, and Java's % keeping the sign. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real (timings vary by machine).

The problem, in real life

Real life In code
48 barfi and 36 ladoos in equal boxes, nothing left over, boxes as big as possible gcd(48, 36) = 12
The teacher crosses out multiples on the blackboard the sieve of Eratosthenes
One grain of rice, doubled on each of 64 chess squares 2^63: past the biggest long
10 o'clock + 5 hours = 3 o'clock (10 + 5) % 12 = 3: modular arithmetic

Every word, from zero

  • Divisor: d divides a if a % d == 0 (no remainder). 12 divides 48.
  • GCD (greatest common divisor): the biggest number that divides both a and b. gcd(48, 36) = 12. Every number divides 0, so gcd(0, 5) = 5.
  • LCM (least common multiple): the smallest number both divide. lcm(a, b) = a / gcd(a, b) * b (divide first, so it does not overflow).
  • Remainder, %: what is left after dividing. 1071 % 462 = 147. In Java the result keeps the sign of the left side: -7 % 3 = -1.
  • Euclid's algorithm: gcd(a, b) = gcd(b, a % b), until b = 0.
  • Prime: a number bigger than 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11 ...
  • Composite: a number bigger than 1 that is not prime (it has a smaller divisor).
  • Trial division: test a number for primality by trying divisors d while d * d <= x.
  • Sieve of Eratosthenes: cross out the multiples of each prime, starting at i * i; what is never crossed is prime.
  • Modulo / modular arithmetic: keep only the remainder after dividing by m, like a clock keeps only the hour.
  • 1e9+7 (1,000,000,007): the usual modulus: it is prime, and the product of two remainders (< 10¹⁸) still fits in a long (max ≈ 9.2 × 10¹⁸).
  • Fast power (binary exponentiation, exponentiation by squaring): compute a^b in O(log b) steps by squaring a and halving b.
  • b & 1: the last bit of b (1 if b is odd). b >>= 1: shift right, i.e. drop the last bit (halve b).
  • Modular inverse: the number x with a * x % m == 1, the "division" of modular arithmetic. When m is prime, x = a^(m-2) % m (Fermat's little theorem).
  • Overflow: a result too big for its type wraps around, often to a negative number.
  • Time Limit Exceeded (TLE): the program ran longer than the judge allows (25 s on the SyntaxPilot compiler).

Problem statements

1. GCD. Given two non-negative integers a and b (up to 10¹⁸, not both 0), return their greatest common divisor.

a b gcd
48 36 12
17 5 1
100 75 25
0 5 5
7 0 7
600851475143 999999999989 1

2. Count primes (LeetCode 204). Given n (up to about 10⁸), count the primes p with 2 ≤ p ≤ n. (LeetCode counts primes strictly less than n; the idea is identical.)

n primes count
10 2 3 5 7 4
30 2 3 5 7 11 13 17 19 23 29 10
1 none 0
2 2 1
1,000,000 78,498
100,000,000 5,761,455

3. Power modulo a prime. Given a and b (up to 10¹⁸), return a^b mod 1,000,000,007.

a b answer
2 10 1024
3 200 136318165
5 0 1
2 10¹⁸ 719476260

Obvious idea 1: GCD by counting down

Start at the smaller number and count down; the first d that divides both is the answer.

import java.util.*;

public class Main {
    static long gcd(long a, long b) {
        for (long d = Math.min(a, b); d >= 1; d--)
            if (a % d == 0 && b % d == 0) return d;
        return 1;
    }
    public static void main(String[] args) {
        System.out.println(gcd(48, 36));
        System.out.println(gcd(17, 5));
        System.out.println(gcd(100, 75));
        System.out.println(gcd(0, 5) + " " + gcd(7, 0));
    }
}
12
1
25
1 1

The first three are right, but 1 1 is wrong: the answers are 5 and 7. With a zero, Math.min(a, b) is 0, the loop never runs, and the function falls through to return 1.

Now two 12-digit numbers:

import java.util.*;

public class Main {
    static long gcd(long a, long b) {
        for (long d = Math.min(a, b); d >= 1; d--)
            if (a % d == 0 && b % d == 0) return d;
        return 1;
    }
    public static void main(String[] args) {
        long t0 = System.nanoTime();
        System.out.println(gcd(600851475143L, 999999999989L));
        System.out.println((System.nanoTime() - t0) / 1000000 + " ms");
    }
}
Time Limit Exceeded

The smaller number is about 6 × 10¹¹, and the two numbers share no divisor except 1, so the loop counts all the way down: 600 billion pairs of divisions.

Euclid's algorithm

Why it works. If d divides a and b, it divides a − b (take equal boxes away, the rest still comes in boxes of d), and so a − 2b, a − 3b, ... down to a % b. The other way round too: anything dividing b and a % b divides a = q·b + a % b. So the two pairs have exactly the same common divisors:

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

By hand: gcd(1071, 462)

a b a % b
1071 462 147 1071 = 2 × 462 + 147
462 147 21 462 = 3 × 147 + 21
147 21 0 147 = 7 × 21
21 0 stop gcd = 21

Three divisions instead of 462 tries. The remainder is always smaller than b, and every two steps the numbers at least halve, so Euclid takes O(log min(a, b)) steps.

import java.util.*;

public class Main {
    static long gcd(long a, long b) {
        while (b != 0) {
            long r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
    public static void main(String[] args) {
        System.out.println(gcd(48, 36));
        System.out.println(gcd(17, 5));
        System.out.println(gcd(100, 75));
        System.out.println(gcd(0, 5) + " " + gcd(7, 0));
        long t0 = System.nanoTime();
        System.out.println(gcd(600851475143L, 999999999989L));
        System.out.println((System.nanoTime() - t0) / 1000000 + " ms");
        System.out.println(48 / gcd(48, 36) * 36);
    }
}
12
1
25
5 7
1
0 ms
144

The zeros are right now (5 7), the 12-digit pair takes 0 ms, and lcm(48, 36) = 48 / 12 * 36 = 144. Java also has BigInteger.gcd, and C++17 has std::gcd / std::lcm in <numeric>; Python has math.gcd and math.lcm.

Obvious idea 2: count primes by trial division

Check each x on its own: try d = 2, 3, 4, ... while d * d <= x. Why only up to √x? Divisors come in pairs (36 = 4 × 9), and one of each pair is at most √x. The (long) cast stops d * d from overflowing near the top of the int range.

import java.util.*;

public class Main {
    static boolean isPrime(int x) {
        if (x < 2) return false;
        for (int d = 2; (long) d * d <= x; d++)
            if (x % d == 0) return false;
        return true;
    }
    static int countPrimes(int n) {
        int count = 0;
        for (int x = 2; x <= n; x++)
            if (isPrime(x)) count++;
        return count;
    }
    public static void main(String[] args) {
        System.out.println(countPrimes(10));
        System.out.println(countPrimes(30));
        System.out.println(countPrimes(1) + " " + countPrimes(2));
        for (int n : new int[]{1000000}) {
            long t0 = System.nanoTime();
            int c = countPrimes(n);
            long ms = (System.nanoTime() - t0) / 1000000;
            System.out.println(n + ": " + c + " primes, " + ms + " ms");
        }
    }
}
4
10
0 1
1000000: 78498 primes, 161 ms

Correct, and a million is quick. Now n = 100,000,000 (the same functions, only the loop changed to new int[]{100000000}):

Time Limit Exceeded

Why is it slow?

Every number is asked, one by one, who divides it. A prime near 10⁸ needs about 10⁴ divisions before we know nothing divides it, and there are 5.7 million primes below 10⁸: tens of billions of divisions, most of them finding nothing. Total: about O(n √n).

The key insight: flip the question (the sieve)

Instead of each number looking for its divisors, each prime crosses out its multiples, like the teacher at the blackboard.

  1. Mark every number from 2 to n as "not crossed".
  2. For i = 2, 3, ... while i * i <= n: if i is not crossed, it is prime; cross i*i, i*i + i, i*i + 2i, ....
  3. Start at i * i: every smaller multiple k·i with k < i was already crossed by the smaller prime factor of k.
  4. Whatever is never crossed is prime.

By hand, n = 30:

Step Crossed now Note
start 1 1 is not prime
i = 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 every even number
i = 3 9 15 21 27 start at 9; 6, 12, 18, 24, 30 already gone
i = 4 nothing 4 is crossed: skip
i = 5 25 start at 25
i = 6 stop 36 > 30

Left: 2 3 5 7 11 13 17 19 23 29: 10 primes.

Solution in Java (the sieve)

import java.util.*;

public class Main {
    static int countPrimes(int n) {
        if (n < 2) return 0;
        boolean[] composite = new boolean[n + 1];
        for (int i = 2; (long) i * i <= n; i++)
            if (!composite[i])
                for (int j = i * i; j <= n; j += i)
                    composite[j] = true;
        int count = 0;
        for (int x = 2; x <= n; x++)
            if (!composite[x]) count++;
        return count;
    }
    public static void main(String[] args) {
        System.out.println(countPrimes(10));
        System.out.println(countPrimes(30));
        System.out.println(countPrimes(1) + " " + countPrimes(2));
        for (int n : new int[]{1000000, 100000000}) {
            long t0 = System.nanoTime();
            int c = countPrimes(n);
            long ms = (System.nanoTime() - t0) / 1000000;
            System.out.println(n + ": " + c + " primes, " + ms + " ms");
        }
    }
}
4
10
0 1
1000000: 78498 primes, 20 ms
100000000: 5761455 primes, 1241 ms

The hundred million that timed out now takes about a second. Each number is crossed once per distinct prime factor, and the sum n/2 + n/3 + n/5 + ... over primes is O(n log log n): almost linear. The array costs n + 1 booleans (about 100 MB for 10⁸ in Java; java.util.BitSet would use 12.5 MB).

Modular arithmetic: numbers too big for a computer

The rice on the 64th square alone is 2⁶³ grains, already past Long.MAX_VALUE (2⁶³ − 1). A problem may even ask for 2^(10¹⁸). So problems say "print the answer modulo 1,000,000,007", and we never build the giant number: we keep only remainders, all the way, like a clock.

Operation Rule Example (m = 12)
Add (a + b) % m = ((a % m) + (b % m)) % m (10 + 5) % 12 = 3
Multiply (a × b) % m = ((a % m) × (b % m)) % m (14 × 5) % 12 = (2 × 5) % 12 = 10
Subtract ((a − b) % m + m) % m ((3 − 5) % 12 + 12) % 12 = 10
Divide multiply by the inverse: a × b^(m−2) % m (m prime) inv(2) mod 1e9+7 = 500000004

Why 1e9+7? It is prime (so every non-zero number has an inverse), and two remainders below it multiply to less than 1.0 × 10¹⁸ < 9.2 × 10¹⁸, so a * b % MOD never overflows a long. Take % MOD after every multiplication, not only at the end.

Obvious idea 3: power by repeated multiplication

import java.util.*;

public class Main {
    static final long MOD = 1_000_000_007L;
    static long power(long a, long b) {
        long result = 1;
        for (long i = 0; i < b; i++)
            result = result * a % MOD;
        return result;
    }
    public static void main(String[] args) {
        System.out.println(power(2, 10));
        System.out.println(power(3, 200));
        System.out.println(power(5, 0));
    }
}
1024
136318165
1

Correct, but power(2, 1000000000000000000L) loops 10¹⁸ times: at a billion steps a second, over 30 years.

Time Limit Exceeded

The key insight: square, and halve the exponent

13 = 8 + 4 + 1 = 1101 in binary, so 3^13 = 3^8 × 3^4 × 3^1, and 3, 3², 3⁴, 3⁸ come from squaring. Walk through the bits of b from the last one: if the bit is 1, multiply the current power into the result; then square a and drop the bit (b >>= 1).

b last bit a (this power) result
13 1 3 3
6 0 9 3
3 1 81 243
1 1 6561 1594323

3^13 = 1,594,323 in 4 steps. For b = 10¹⁸ (about 60 bits): about 60 steps.

Solution in Java (fast power and the inverse)

import java.util.*;

public class Main {
    static final long MOD = 1_000_000_007L;
    static long power(long a, long b) {
        long result = 1;
        a %= MOD;
        while (b > 0) {
            if ((b & 1) == 1) result = result * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return result;
    }
    public static void main(String[] args) {
        System.out.println(power(2, 10));
        System.out.println(power(3, 200));
        System.out.println(power(5, 0));
        System.out.println(power(2, 1000000000000000000L));
        long inv2 = power(2, MOD - 2);
        System.out.println(inv2 + " " + 2 * inv2 % MOD);
    }
}
1024
136318165
1
719476260
500000004 1

500000004 is the modular inverse of 2: 2 × 500000004 = 1,000,000,008 ≡ 1 (mod 1e9+7). Fermat's little theorem says a^(p−1) ≡ 1 (mod p) for a prime p and a not divisible by p, so a^(p−2) is 1/a.

The same solutions in C++

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1'000'000'007LL;

long long gcd_(long long a, long long b) {      // Euclid
    while (b != 0) { long long r = a % b; a = b; b = r; }
    return a;
}

int countPrimes(int n) {                        // sieve of Eratosthenes
    if (n < 2) return 0;
    vector<bool> composite(n + 1, false);
    for (long long i = 2; i * i <= n; i++)
        if (!composite[i])
            for (long long j = i * i; j <= n; j += i)
                composite[j] = true;
    int count = 0;
    for (int x = 2; x <= n; x++)
        if (!composite[x]) count++;
    return count;
}

long long power(long long a, long long b) {     // fast power, mod MOD
    long long result = 1;
    a %= MOD;
    while (b > 0) {
        if (b & 1) result = result * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return result;
}

int main() {
    cout << gcd_(48, 36) << " " << gcd_(17, 5) << " " << gcd_(100, 75) << "\n";
    cout << gcd_(0, 5) << " " << gcd_(7, 0) << " " << gcd_(600851475143LL, 999999999989LL) << "\n";
    cout << 48 / gcd_(48, 36) * 36 << "\n";
    cout << countPrimes(10) << " " << countPrimes(30) << " " << countPrimes(1) << " " << countPrimes(2) << "\n";
    cout << countPrimes(1000000) << " " << countPrimes(100000000) << "\n";
    cout << power(2, 10) << " " << power(3, 200) << " " << power(5, 0) << "\n";
    cout << power(2, 1000000000000000000LL) << "\n";
    long long inv2 = power(2, MOD - 2);
    cout << inv2 << " " << 2 * inv2 % MOD << "\n";
}
12 1 25
5 7 1
144
4 10 0 1
78498 5761455
1024 136318165 1
719476260
500000004 1

vector<bool> packs one bit per number. The loop variables are long long, so i * i cannot overflow.

The same solutions in Python

import math

MOD = 1_000_000_007


def gcd(a, b):                     # Euclid
    while b != 0:
        a, b = b, a % b
    return a


def count_primes(n):               # sieve of Eratosthenes
    if n < 2:
        return 0
    composite = bytearray(n + 1)
    i = 2
    while i * i <= n:
        if not composite[i]:
            composite[i * i::i] = b"\x01" * len(range(i * i, n + 1, i))
        i += 1
    return n - 1 - sum(composite[2:])


def power(a, b):                   # fast power, mod MOD
    result = 1
    a %= MOD
    while b > 0:
        if b & 1:
            result = result * a % MOD
        a = a * a % MOD
        b >>= 1
    return result


print(gcd(48, 36), gcd(17, 5), gcd(100, 75))
print(gcd(0, 5), gcd(7, 0), gcd(600851475143, 999999999989))
print(48 // gcd(48, 36) * 36, math.gcd(48, 36), math.lcm(48, 36))
print(count_primes(10), count_primes(30), count_primes(1), count_primes(2))
print(count_primes(1_000_000), count_primes(10_000_000))
print(power(2, 10), power(3, 200), power(5, 0))
print(power(2, 10**18), pow(2, 10**18, MOD))
inv2 = power(2, MOD - 2)
print(inv2, 2 * inv2 % MOD, pow(2, -1, MOD))
12 1 25
5 7 1
144 12 144
4 10 0 1
78498 664579
1024 136318165 1
719476260 719476260
500000004 1 500000004

Python integers never overflow, and the built-ins do the same jobs: math.gcd, math.lcm, pow(a, b, m) (fast power) and pow(a, -1, m) (the inverse, Python 3.8+). The slice assignment composite[i*i::i] = ... crosses out a whole row of multiples at C speed. Pure Python is still slow for 10⁸ (it needs a 100 MB bytearray), so it is run here up to 10⁷.

Three real bugs

Bug 1: i <= n instead of (long) i * i <= n in the sieve.

import java.util.*;

public class Main {
    static int countPrimes(int n) {
        if (n < 2) return 0;
        boolean[] composite = new boolean[n + 1];
        for (int i = 2; i <= n; i++)
            if (!composite[i])
                for (int j = i * i; j <= n; j += i)
                    composite[j] = true;
        int count = 0;
        for (int x = 2; x <= n; x++)
            if (!composite[x]) count++;
        return count;
    }
    public static void main(String[] args) {
        System.out.println(countPrimes(1000000));
    }
}
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -2146737495 out of bounds for length 1000001
    at Main.countPrimes(Main.java:10)
    at Main.main(Main.java:17)

When i passes 46,340, i * i is bigger than Integer.MAX_VALUE (2,147,483,647) and wraps to a negative number, which j <= n happily accepts. Fix: loop while (long) i * i <= n (then i * i in the inner loop is at most n), or make j a long.

Bug 2: forgetting % MOD when squaring.

import java.util.*;

public class Main {
    static final long MOD = 1_000_000_007L;
    static long power(long a, long b) {
        long result = 1;
        a %= MOD;
        while (b > 0) {
            if ((b & 1) == 1) result = result * a % MOD;
            a = a * a;
            b >>= 1;
        }
        return result;
    }
    public static void main(String[] args) {
        System.out.println(power(2, 10));
        System.out.println(power(3, 200));
        System.out.println(power(5, 0));
    }
}
1024
-333352893
1

2^10 still looks right because the numbers stay small. For 3^200, a keeps squaring until the long overflows, and the answer comes out negative.

Bug 3: subtracting under a modulus.

import java.util.*;

public class Main {
    static final long MOD = 1_000_000_007L;
    static long power(long a, long b) {
        long result = 1;
        a %= MOD;
        while (b > 0) {
            if ((b & 1) == 1) result = result * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return result;
    }
    public static void main(String[] args) {
        long x = power(2, 30), y = power(3, 20);
        System.out.println(x + " " + y);
        System.out.println((x - y) % MOD);
    }
}
73741817 486784380
-413042563

Java's % keeps the sign of the left side, so a negative difference stays negative. Fix:

        System.out.println(((x - y) % MOD + MOD) % MOD);
73741817 486784380
586957444

Complexity

Problem Obvious way Time Better way Time Space
GCD count down from min(a, b) O(min(a, b)): TLE at 10¹² Euclid O(log min(a, b)) O(1)
Count primes ≤ n trial division to √x O(n √n): TLE at 10⁸ sieve O(n log log n) O(n)
a^b mod m multiply b times O(b): TLE at 10¹⁸ fast power O(log b) O(1)
Is one x prime? trial division O(√x) (fine for one number) O(1)

Common mistakes

Mistake What you see (real) Why Fix
GCD by counting down from min(a, b) gcd(0, 5) prints 1; TLE on big numbers the loop never runs for 0; 600 billion tries Euclid: gcd(b, a % b)
Sieve loop for (int i = 2; i <= n; i++) java.lang.ArrayIndexOutOfBoundsException: Index -2146737495 out of bounds for length 1000001 i * i overflows an int (long) i * i <= n
a = a * a; without % MOD -333352893 the long overflows a = a * a % MOD
(x - y) % MOD -413042563 % keeps the sign of the left side ((x - y) % MOD + MOD) % MOD
lcm = a * b / gcd(a, b) overflow for big a, b a * b is computed first a / gcd(a, b) * b
Starting the sieve's inner loop at 2 * i correct, but slower re-crosses numbers already crossed start at i * i
int instead of long for results wrong answers past 2.1 × 10⁹ int max is 2,147,483,647 long for anything multiplied

Mini project: the sweet shop box planner

Read how many sweets of each kind the shop has, find the biggest box size that packs every kind with nothing left over (the GCD of all the counts), and how many boxes that makes.

import java.util.*;

public class Main {
    static long gcd(long a, long b) { while (b != 0) { long r = a % b; a = b; b = r; } return a; }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int k = in.nextInt();
        long[] counts = new long[k];
        long g = 0;
        for (int i = 0; i < k; i++) { counts[i] = in.nextLong(); g = gcd(g, counts[i]); }
        System.out.println("Biggest box: " + g + " sweets");
        long boxes = 0;
        for (long c : counts) boxes += c / g;
        System.out.println("Boxes needed: " + boxes);
    }
}

Input 3 48 36 120 (barfi, ladoos, jalebis):

Biggest box: 12 sweets
Boxes needed: 17

Extend it: print, for each kind, how many boxes it fills, and list the box sizes that work (every divisor of the GCD).

Practice

1. Count Primes (LeetCode 204). The sieve above, counting primes strictly below n.

2. Pow(x, n) (LeetCode 50). Fast power on a double; a negative n means 1 / x^|n|. Careful: -Integer.MIN_VALUE does not fit in an int.

3. GCD of an array. Fold gcd over the array, starting from 0 (gcd(0, x) = x).

4. Super Pow (LeetCode 372). a^b mod 1337 where b is a huge number given as an array of digits. Use a^(10x + d) = (a^x)^10 × a^d.

Solutions (2, 3 and 4)
import java.util.*;

public class Main {
    // Pow(x, n), LeetCode 50: fast power on doubles; negative n means 1 / x^|n|.
    static double myPow(double x, int n) {
        long b = n;                       // long: -Integer.MIN_VALUE does not fit in an int
        if (b < 0) { x = 1 / x; b = -b; }
        double result = 1;
        while (b > 0) {
            if ((b & 1) == 1) result *= x;
            x *= x;
            b >>= 1;
        }
        return result;
    }
    // GCD of an array: fold gcd over it.
    static long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); }
    static long gcdAll(long[] v) {
        long g = 0;                       // gcd(0, x) = x, so 0 is the starting value
        for (long x : v) g = gcd(g, x);
        return g;
    }
    // Super Pow, LeetCode 372: a^b mod 1337, b given as a digit array.
    static int powMod(int a, int k, int m) {
        int r = 1; a %= m;
        while (k > 0) { if ((k & 1) == 1) r = r * a % m; a = a * a % m; k >>= 1; }
        return r;
    }
    static int superPow(int a, int[] b) {
        int r = 1;
        for (int d : b) r = powMod(r, 10, 1337) * powMod(a, d, 1337) % 1337;   // a^(10x + d) = (a^x)^10 * a^d
        return r;
    }
    public static void main(String[] args) {
        System.out.println(myPow(2.0, 10));
        System.out.println(myPow(2.0, -2));
        System.out.println(myPow(1.0, Integer.MIN_VALUE));
        System.out.println(gcdAll(new long[]{48, 36, 120}));
        System.out.println(gcdAll(new long[]{0, 0, 9}));
        System.out.println(superPow(2, new int[]{3}));
        System.out.println(superPow(2, new int[]{1, 0}));
        System.out.println(superPow(2147483647, new int[]{2, 0, 0}));
    }
}
1024.0
0.25
1.0
12
9
8
1024
1198

Quick quiz

What does System.out.println(-7 % 3); print? A) 2 B) -1 C) 1 D) -2

Answer

B) -1. Java's % keeps the sign of the left side: -7 = -2 × 3 + (-1). To get 2, write ((-7 % 3) + 3) % 3. (Python's % follows the sign of the right side and prints 2.)

Interview questions

  1. Why does gcd(a, b) = gcd(b, a % b) hold? Any common divisor of a and b divides a − q·b = a % b, and any common divisor of b and a % b divides a. Same set of common divisors, same greatest one.
  2. How many steps does Euclid take? O(log min(a, b)); the worst case is two consecutive Fibonacci numbers.
  3. Why does the sieve start crossing at i * i? Every smaller multiple k·i (k < i) has a prime factor smaller than i, so it is already crossed.
  4. Complexity of the sieve? O(n log log n) time, O(n) space.
  5. How do you test one big number for primality? Trial division up to √x, O(√x); for 64-bit numbers, Miller–Rabin.
  6. What is fast power, and its complexity? Square the base and halve the exponent, multiplying in the base when the bit is 1: O(log b).
  7. Why mod 1e9+7? It is prime (inverses exist) and the product of two remainders fits in a 64-bit integer.
  8. How do you divide under a modulus? Multiply by the modular inverse; for a prime modulus p, inv(a) = a^(p−2) mod p (Fermat). Otherwise the extended Euclidean algorithm, when gcd(a, m) = 1.
  9. How do you handle negative numbers with % in Java? ((x % m) + m) % m, or Math.floorMod(x, m).

Glossary

Term Meaning
Divisor d divides a when a % d == 0
GCD Greatest common divisor: the biggest number dividing both
LCM Least common multiple: a / gcd(a, b) * b
Remainder % What is left after division; in Java it keeps the left side's sign
Euclid's algorithm gcd(a, b) = gcd(b, a % b) until b = 0
Prime Bigger than 1, divisible only by 1 and itself
Composite Bigger than 1 and not prime
Trial division Testing primality with divisors up to √x
Sieve of Eratosthenes Cross out each prime's multiples from i * i; the rest are prime
Modular arithmetic Arithmetic that keeps only remainders mod m, like a clock
1e9+7 1,000,000,007: the usual prime modulus
Fast power Binary exponentiation: square and halve, O(log b)
b & 1 / b >>= 1 The last bit of b / drop the last bit (halve)
Modular inverse x with a × x ≡ 1 (mod m); a^(m−2) for prime m
Fermat's little theorem a^(p−1) ≡ 1 (mod p) for prime p, p ∤ a
Overflow A value past its type's maximum wraps around
TLE Time Limit Exceeded

Summary

  • GCD: counting down is wrong for 0 and O(min(a, b)); Euclid gcd(b, a % b) is O(log). LCM = a / gcd * b.
  • Primes: trial division is O(n √n); the sieve crosses each prime's multiples from i * i in O(n log log n). Keep i * i in a long.
  • Huge answers: work mod 1e9+7, taking % MOD after every multiplication; after a subtraction, add MOD before the last %.
  • Fast power: square and halve, O(log b); with a prime modulus it also gives the inverse a^(MOD−2).
  • Next episode: string matching with KMP: finding a word in a huge text without starting over.