Math & Number Theory

gcd, primes, mod 10⁹+7, fast power, nCr and digit tricks: small math that unlocks big interview problems.

intermediate~75 min6 simulations9 problems

▶ guided lesson ⚡ 1-minute summary ↻ 15 recall cards

before this: Big-O · Recursion

Section

01 · why it exists

Why this exists, and the weight it carries

sincec. 300 BCE

Euclid's algorithm (gcd and lcm)

Euclid of Alexandria (Elements, Book VII); the method is probably older

Euclid's Elements (c. 300 BCE), Book VII, Propositions 1–2, finds the "greatest common measure" of two numbers by repeatedly taking the smaller from the larger. Historians think Euclid collected the method rather than invented it. In 1844 Gabriel Lamé proved it never needs more than 5 × (digits of the smaller number) division steps, a result often called the start of computational complexity theory. Knuth calls it the oldest nontrivial algorithm that is still in use.

the problem it solvedFind the largest number that divides two numbers exactly — without listing all their divisors.

its jobs today

Reducing fractions and ratios to one canonical form: a 1920 × 1080 screen is 16:9 because gcd(1920, 1080) = 120; Max Points on a Line uses the same trick for directions.
The extended version computes modular inverses — the step that derives an RSA private key.
Big numbers in the JDK: BigInteger.gcd runs Euclid while the numbers differ in length, then binary GCD.

the weight it carries

Illustrative: two numbers near 10¹⁸ (a long). Subtracting the smaller from the larger: gcd(10¹⁸, 1) needs 10¹⁸ − 1 subtractions — about 31.7 years at 10⁹ per second. Euclid with %: the worst case in a long is the Fibonacci pair F₉₂, F₉₁, which takes 90 divisions (Lamé's bound: 5 × 19 digits = 95).

without it

Exact fractions would need slow divisor searches, and RSA key setup (which needs a modular inverse) would lose its fast path.

when · why · how

when: You need a gcd or lcm, a reduced fraction or direction, or to know whether two numbers share a factor.
why: O(log min(a, b)) divisions and O(1) space, against O(min(a, b)) for trying every divisor.
how: while (b != 0) { int r = a % b; a = b; b = r; } return a; · lcm = (long) a / gcd(a, b) * b · BigInteger.gcd for huge values.

since3rd century BCE (recorded in the 2nd century CE)

Sieve of Eratosthenes

Eratosthenes of Cyrene (c. 276–194 BCE); recorded by Nicomachus of Gerasa

Eratosthenes became the third librarian at Alexandria around 240 BCE. His sieve reaches us through Nicomachus of Gerasa's Introduction to Arithmetic, an early 2nd-century CE book that credits him. Write the numbers down and strike out the multiples of each prime; what survives is prime. In modified forms it is still a working tool in number-theory research.

the problem it solvedList every prime up to n without testing each number separately.

its jobs today

Precomputing primes (or smallest prime factors) once, so later prime checks are O(1) and factorisations take O(log n) steps.
Prime generation for cryptography: the JDK's BigInteger.probablePrime sieves candidates with java.math.BitSieve before the expensive primality test.

the weight it carries

Illustrative: all primes up to 10 lakh (10⁶). Trial division of every number (stopping at the first divisor or at √k): 67,740,404 divisions. The sieve: 2,122,048 crossings — about 32× less work — for a 1 MB boolean[]. Result: 78,498 primes.

without it

Every "is it prime?" question over many numbers becomes a √n loop each time.

when · why · how

when: You need many primes, or prime checks for many numbers up to a limit N (≈ 10⁷ fits in memory).
why: O(n log log n) once, then O(1) per lookup, paid for with O(n) memory; trial division is O(√n) per query with no memory.
how: boolean[] isPrime = new boolean[n + 1]; mark 2..n true; for p while (long) p * p <= n, if isPrime[p], cross out p², p² + p, ….

since1801

Modular arithmetic (and why 10⁹+7)

Carl Friedrich Gauss (Disquisitiones Arithmeticae); Pierre de Fermat and Leonhard Euler before him

Remainders are ancient, but Gauss turned them into a systematic arithmetic in Disquisitiones Arithmeticae (1801): numbers with the same remainder mod m behave the same under + and ×. Earlier, in a letter of 18 October 1640 to Frénicle de Bessy, Fermat stated that a^(p−1) leaves remainder 1 for a prime p that does not divide a; Euler published the first proof in 1736. That "little theorem" is why division works modulo a prime.

the problem it solvedCompute with numbers far too large to write down by keeping only their remainders — and still add, subtract, multiply (and, for a prime modulus, divide) correctly.

its jobs today

Exact answers to huge counts in interviews and contests: "return it modulo 10⁹+7".
Wrap-around indices: HashMap picks a bucket with (n − 1) & hash (a remainder by a power of two), and a circular buffer moves with (i + 1) % capacity.
Check digits: ISBN-10 uses arithmetic mod 11 and ISBN-13 mod 10 to catch typos.

the weight it carries

Illustrative: the number of subsets of 100 items is 2¹⁰⁰ — 31 digits, while a long holds 19. Mod p = 10⁹+7 every value stays below 1,000,000,007. Two residues add to at most 2,000,000,012 < 2,147,483,647 (fits an int) and multiply to at most (10⁹+6)² = 1,000,000,012,000,000,036 < 9,223,372,036,854,775,807 (fits a long).

without it

Every count would need BigInteger — or a bare int multiply would silently overflow and return garbage.

when · why · how

when: The statement says "modulo 10⁹+7", or you need wrap-around indices, hashing or cyclic behaviour.
why: Every operation stays O(1) on fixed-size numbers instead of growing BigIntegers; the price is that you can no longer compare the real numbers' sizes.
how: (a + b) % M, (long) a * b % M, Math.floorMod(a - b, M); to divide, multiply by modPow(b, M - 2, M).

sincec. 2nd century BCE (antecedent) · 1427 (general method)

Fast power (binary exponentiation)

Piṅgala (Chandaḥśāstra); Jamshīd al-Kāshī (Miftāḥ al-Ḥisāb)

Piṅgala's Chandaḥśāstra, a Sanskrit work on poetic metre, computes 2ⁿ — the number of n-syllable metres — recursively: if n can be halved, halve it and square the result; if not, subtract 1 and double. Jayant Shah calls this divide-and-conquer. A 2026 survey (Aydin et al.) agrees it rests on the same principle as binary exponentiation but notes Piṅgala used it only inside that counting problem; it credits al-Kāshī's Miftāḥ al-Ḥisāb (1427) with presenting square-and-multiply explicitly as a general method. Knuth's TAOCP calls the method "quite ancient".

the problem it solvedCompute a huge power — 2ⁿ metres, or aᵉ mod m with e in the billions — without multiplying e times.

its jobs today

Public-key cryptography: RSA and Diffie–Hellman are built on aᵉ mod m with numbers hundreds of digits long (BigInteger.modPow).
Modular inverses (a^(p−2) mod p), nCr mod p, and matrix powers that compute Fibonacci-style recurrences in O(log n).

the weight it carries

Illustrative: aᵉ mod m with e = 10¹⁸. One multiplication at a time: 10¹⁸ multiplications — about 31.7 years at 10⁹ per second. Fast power: 10¹⁸ has 60 bits, so 60 squarings plus at most 60 multiplications — at most 120.

without it

RSA and Diffie–Hellman would be unusable: their exponents have hundreds of digits.

when · why · how

when: xⁿ with large n, especially aⁿ mod m; inverses modulo a prime; any step applied n times that composes (like a matrix).
why: O(log n) multiplications instead of O(n); the loop uses O(1) space, the recursive version O(log n) stack.
how: while (e > 0) { if ((e & 1) == 1) r = r * b % m; b = b * b % m; e >>= 1; } in long, or BigInteger.modPow.

since2nd century BCE (Piṅgala) · 10th century CE (Halāyudha)

Combinations nCr and Pascal's triangle (Meru-prastāra)

Piṅgala; his commentator Halāyudha; later Śrīdhara, al-Karajī, Jia Xian, Yang Hui and Blaise Pascal

Piṅgala's Chandaḥśāstra asks how many n-syllable metres have k short syllables — the binomial coefficients nCk — and scholars such as Jayant Shah and Amba Kulkarni read its terse sūtras as giving an algorithm for them. Halāyudha's 10th-century commentary reads Piṅgala's last sūtra as the Meru-prastāra ("mountain" arrangement): a triangle where each cell is the sum of the two above it. Historians differ on that reading — Albrecht Weber rejected it, and Jayant Shah agrees with Weber about Halāyudha but argues the construction can still be traced to Piṅgala. Śrīdhara (often dated c. 750 CE, though some historians place him later) gave the modern formula for nCk, and the same triangle appears with al-Karajī, Jia Xian and Yang Hui, and in Pascal's Traité du triangle arithmétique, published in 1665.

the problem it solvedCount arrangements — how many ways to choose r things from n — without listing them.

its jobs today

Counting paths, subsets and teams: Unique Paths (LC 62) is C(m + n − 2, m − 1), and "how many ways … modulo 10⁹+7" questions are nCr with factorial tables.
Probability: the chance of exactly r successes in n tries is nCr · pʳ · (1 − p)ⁿ⁻ʳ — the binomial distribution behind A/B-test statistics.

the weight it carries

Illustrative: C(10⁵, 5·10⁴) mod 10⁹+7. A Pascal table to row 10⁵ has about 10⁵ × 10⁵ / 2 = 5·10⁹ cells — 40 GB of longs. Factorial tables: 2 × 10⁵ multiplications plus one inverse (about 30 squarings), then 2 multiplications per nCr. Exact values: C(66, 33) still fits a long; C(67, 33) ≈ 1.42·10¹⁹ does not.

without it

Counting questions would need enumeration (2ⁿ subsets) or BigInteger arithmetic everywhere.

when · why · how

when: "How many ways", paths on a grid, choosing teams, the probability of r successes.
why: Pascal: O(n²) time and space, additions only — fine for small n. Factorials mod p: O(n) once, then O(1) per query.
how: c[n][r] = c[n−1][r−1] + c[n−1][r], or fact[n] * invFact[r] % M * invFact[n − r] % M.

sinceby the end of the 6th century CE

Place-value digits (% 10 and / 10)

Indian mathematicians and scribes (no single inventor is known)

The decimal place-value system, where a digit's position decides its weight, grew up in India. A donation charter dated 594 CE already uses it, though some historians suspect that date was added later; the Gwalior inscription of 876 CE is the first example nobody disputes. The numerals then travelled through the Arab world — around 1030 al-Bīrūnī wrote that the Arabs used the best of the Indian figures — and on to Europe. Because each place is worth ten times the next, x % 10 is the units digit and x / 10 shifts every digit one place right.

the problem it solvedWrite any number with ten symbols, and do arithmetic column by column.

its jobs today

Number ↔ text: the JDK's Integer.toString peels digits by division, two per step.
Validation: check digits (ISBN, and many account and card numbers) are computed digit by digit.

the weight it carries

Illustrative: printing 10 lakh 7-digit order ids. One digit per division: 7,000,000 divisions. The JDK's two-digits-per-step loop: 4 divisions per id (3 by 100, 1 by 10), so 4,000,000. An int has at most 10 digits and a long 19, so a digit loop never runs more than 19 times.

without it

Every reverse, palindrome or digit-sum check would allocate a String per number — and the overflow trap would hide inside Long.parseLong.

when · why · how

when: Reverse, palindrome or digit sums "without converting to a string", base conversion, check digits.
why: O(number of digits) time and O(1) space with no allocation; the String route is also O(digits) but allocates every call.
how: int d = x % 10; x /= 10; pops, rev = rev * 10 + d pushes; check rev > Integer.MAX_VALUE / 10 before pushing.

since?

Weighted random pick (prefix sums + binary search)

Choosing by cumulative weights (inverse-transform sampling on a discrete distribution) is folklore in probability and simulation; we found no single inventor to credit. The O(1)-per-pick alias method is credited to Alastair J. Walker (1974).

its jobs today

Load balancing: NGINX's random method picks an upstream server "taking into account weights of servers".
Traffic splits and sampling: send about 10% of users to a canary build, show items in proportion to a score, drop rare game loot less often.

the weight it carries

Illustrative: 10⁴ weighted servers and 10 lakh (10⁶) picks. Linear scan: up to 10⁴ comparisons per pick, so up to 10¹⁰ in total. Binary search: ⌈log₂ 10⁴⌉ = 14 per pick, so 1.4·10⁷. A ticket array would need one slot per unit of weight: up to 10⁹ ints (about 4 GB) at LeetCode's limits.

without it

Weighted choices would need huge ticket arrays or an O(n) scan per request.

when · why · how

when: Pick with probability proportional to weight, many times, while the weights stay fixed.
why: O(n) build once, O(log n) per pick, O(n) memory. The alias method reaches O(1) per pick with a more complex setup.
how: prefix[i] = sum while summing; int t = random.nextInt(total) + 1; then a lower-bound binary search (or Arrays.binarySearch, fixing its negative result).

02 · plain english

The idea in 30 seconds

Many interview problems hide a little number theory: a gcd, a prime check, a remainder, a power, a count of ways, a digit loop.

Each one has a tiny classic algorithm that turns a slow loop into O(log n) or close: Euclid, the sieve, fast power, Fermat's inverse.

Java adds one rule on top: know the overflow limits (int ≈ 2.1·10⁹, long ≈ 9.2·10¹⁸) and check before you multiply.

picture this

Modular arithmetic is the 12-hour clock on your taskbar: 3 hours after 11 o'clock it shows 2, not 14. % m lets a count grow forever while the stored value stays in 0..m−1. Your CPU's int already wraps like this at 2³² — silently — which is why we choose the wrap ourselves.

03 · remember

What you must know

Euclid: gcd(a, b) = gcd(b, a % b), stop when b is 0. O(log min(a, b)): at most 91 divisions even for two longs (90 when a ≥ b). lcm = a / gcd * b (divide first).
Sieve of Eratosthenes: for each prime p with p² ≤ n, cross out p², p² + p, …. O(n log log n) time, O(n) memory. For a single number, trial division up to √n is enough.
Modulo: reduce after every + and ×: (a + b) % M, (long) a * b % M. Java's % can be negative, so use ((x % M) + M) % M or Math.floorMod.
Why 10⁹+7: it is prime (so division works through Fermat), a residue fits in an int, and the product of two residues (< 10¹⁸) fits in a long.
Fast power: square the base each step and multiply it in when the exponent's lowest bit is 1. O(log e). For a prime p, a^(p−2) mod p is the inverse of a.
nCr: Pascal's rule nCr = (n−1)C(r−1) + (n−1)Cr for small n; factorials and inverse factorials mod p for n up to 10⁵ and beyond.
Digits: x % 10 reads the last digit, x / 10 drops it, rev * 10 + d appends one. Guard against overflow before the multiply.
Weighted random: prefix sums turn weights into ticket ranges; a binary search finds the owner of a random ticket in O(log n).

04 · see it

Play with it in 3D

Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.

sim

Euclid's gcd step by step

The pair (a, b) slides left as (b, a % b). Watch the bars collapse in a handful of divisions.

loading simulation…

javajava.math.BigInteger · java.util.*

1class Euclid {2    /** Greatest common divisor of two non-negative ints. gcd(a, 0) = a. */3    static int gcd(int a, int b) {4        while (b != 0) {5            int r = a % b;6            a = b;7            b = r;8        }9        return a;10    }11 12    /** Least common multiple. Divide first, then multiply, in long: a / gcd * b never overflows early. */13    static long lcm(int a, int b) {14        if (a == 0 || b == 0) return 0;15        return (long) a / gcd(a, b) * b;16    }17}

sim

Sieve of Eratosthenes on a number board

Each prime crosses out its multiples starting at p². Whatever survives is prime.

loading simulation…

javajava.math.BigInteger · java.util.*

1class Sieve {2    /** isPrime[i] for every 0 <= i <= n, in O(n log log n). */3    static boolean[] sieve(int n) {4        boolean[] isPrime = new boolean[n + 1];5        for (int i = 2; i <= n; i++) isPrime[i] = true;6        for (int p = 2; (long) p * p <= n; p++) {7            if (!isPrime[p]) continue;8            for (int m = p * p; m <= n; m += p) isPrime[m] = false;9        }10        return isPrime;11    }12 13    static List<Integer> primesUpTo(int n) {14        boolean[] isPrime = sieve(n);15        List<Integer> primes = new ArrayList<>();16        for (int i = 2; i <= n; i++) if (isPrime[i]) primes.add(i);17        return primes;18    }19}

sim

Fast power, bit by bit

Read the exponent's bits from the right. Square the base every step; multiply it in only on a 1-bit.

loading simulation…

javajava.math.BigInteger · java.util.*

1class FastPower {2    /** base^exp mod m by binary exponentiation: about 2 * log2(exp) multiplications. */3    static long modPow(long base, long exp, long mod) {4        long result = 1 % mod;5        base = ((base % mod) + mod) % mod;6        while (exp > 0) {7            if ((exp & 1) == 1) result = result * base % mod;8            base = base * base % mod;9            exp >>= 1;10        }11        return result;12    }13 14    /** Inverse of a modulo a PRIME p (Fermat): a^(p-2), valid when a % p != 0. */15    static long modInverse(long a, long p) {16        return modPow(a, p - 2, p);17    }18}

sim

Pascal's triangle (Meru-prastāra) as a 3D landscape

Every inside cell is the sum of the two cells above it. Row n adds up to 2ⁿ.

loading simulation…

javajava.math.BigInteger · java.util.*

1class Pascal {2    /** c[n][r] = nCr for every 0 <= r <= n <= rows. Exact in long up to n = 66. */3    static long[][] table(int rows) {4        long[][] c = new long[rows + 1][];5        for (int n = 0; n <= rows; n++) {6            c[n] = new long[n + 1];7            c[n][0] = c[n][n] = 1;8            for (int r = 1; r < n; r++) {9                c[n][r] = c[n - 1][r - 1] + c[n - 1][r];10            }11        }12        return c;13    }14}

sim

Reverse Integer: pop, check, push

Digits leave x from the right and join rev. The guard fires before rev × 10 could overflow.

loading simulation…

javajava.util.*

1class Solution {2    public int reverse(int x) {3        int rev = 0;4        while (x != 0) {5            int pop = x % 10;6            x /= 10;7            if (rev > Integer.MAX_VALUE / 10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;8            if (rev < Integer.MIN_VALUE / 10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;9            rev = rev * 10 + pop;10        }11        return rev;12    }13}

sim

Weighted pick with prefix sums

Index i owns w[i] tickets. A random ticket's owner is found by binary search on the prefix sums.

loading simulation…

javajava.util.*

1class Solution {2    private final int[] prefix;                       // index i owns tickets prefix[i-1]+1 .. prefix[i]3    private final Random random = new Random();4 5    public Solution(int[] w) {6        prefix = new int[w.length];7        int sum = 0;                                  // at most 10^4 * 10^5 = 10^9: fits in an int8        for (int i = 0; i < w.length; i++) {9            sum += w[i];10            prefix[i] = sum;11        }12    }13 14    public int pickIndex() {15        int ticket = random.nextInt(prefix[prefix.length - 1]) + 1;   // 1..total, all equally likely16        return indexFor(ticket);17    }18 19    int indexFor(int ticket) {                        // the first i with prefix[i] >= ticket20        int lo = 0, hi = prefix.length - 1;21        while (lo < hi) {22            int mid = lo + (hi - lo) / 2;23            if (prefix[mid] < ticket) lo = mid + 1;24            else hi = mid;25        }26        return lo;27    }28}

05 · cost

Time & space, explained

The number-theory toolkit
	Time	Extra space	why
gcd by repeated subtraction	O(max(a, b))	O(1)	gcd(10¹⁸, 1) needs 10¹⁸ − 1 subtractions.
gcd by Euclid (with %)	O(log min(a, b))	O(1)	Every two steps the larger number drops below half. Lamé: at most 5 × (digits of the smaller).
Is n prime? (trial division)	O(√n)	O(1)	Divisors come in pairs d × (n / d), and one of each pair is ≤ √n.
All primes ≤ n (sieve)	O(n log log n)	O(n)	Each prime p crosses about n / p cells; Σ n / p over primes is n log log n. n = 10⁶: 2,122,048 crossings.
aᵉ mod m, one multiply at a time	O(e)	O(1)	e = 10¹⁸ would take about 31.7 years at 10⁹ multiplications per second.
aᵉ mod m, fast power	O(log e)	O(1)	One loop step per bit of e: 60 steps for e = 10¹⁸.
Inverse mod a prime p (Fermat)	O(log p)	O(1)	It is one fast power: a^(p−2) mod p.
Pascal's table up to row n	O(n²)	O(n²)	n(n + 1)/2 cells. Row 10⁵ would need 5·10⁹ cells, about 40 GB of longs.
nCr mod p with factorial tables	O(n + log p) once, O(1) per query	O(n)	n multiplications for fact[], one Fermat inverse, n more for invFact[]; each nCr is 2 multiplications.
Peel the digits of x	O(log₁₀ x)	O(1)	An int has at most 10 digits, a long at most 19.

Random Pick with Weight (n weights, total S)
	Build	Per pick	Space	why
Ticket array (index i written w[i] times)	O(S)	O(1)	O(S)	S can reach 10⁴ × 10⁵ = 10⁹ ints, about 4 GB.
Prefix sums + linear scan	O(n)	O(n)	O(n)	Walk prefix[] until it reaches the ticket.
Prefix sums + binary search	O(n)	O(log n)	O(n)	prefix[] is strictly increasing (every w[i] ≥ 1): 14 probes for n = 10⁴.

06 · java

Raw vs Collections Framework

gcd: write it vs call it

javaEuclid's loop + lcmjava.math.BigInteger · java.util.*

1class Euclid {2    /** Greatest common divisor of two non-negative ints. gcd(a, 0) = a. */3    static int gcd(int a, int b) {4        while (b != 0) {5            int r = a % b;6            a = b;7            b = r;8        }9        return a;10    }11 12    /** Least common multiple. Divide first, then multiply, in long: a / gcd * b never overflows early. */13    static long lcm(int a, int b) {14        if (a == 0 || b == 0) return 0;15        return (long) a / gcd(a, b) * b;16    }17}

javaBigInteger.gcd / one-line recursionjava.math.BigInteger · java.util.*

1class Library {2    static int gcd(int a, int b) {3        return BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).intValue(); // works for any size4    }5 6    static long gcdRecursive(long a, long b) {7        return b == 0 ? a : gcdRecursive(b, a % b); // one line, about 90 calls at most for a long8    }9}

Java has no Math.gcd. Write the four-line loop from memory; interviewers expect it.
BigInteger.gcd runs Euclid while the numbers differ a lot in length, then switches to binary GCD (MutableBigInteger.hybridGCD in OpenJDK).
lcm: (long) a / gcd(a, b) * b. Dividing first keeps the intermediate value small; a * b / gcd can overflow even when the lcm fits.

The sieve

javaboolean[] sievejava.math.BigInteger · java.util.*

1class Sieve {2    /** isPrime[i] for every 0 <= i <= n, in O(n log log n). */3    static boolean[] sieve(int n) {4        boolean[] isPrime = new boolean[n + 1];5        for (int i = 2; i <= n; i++) isPrime[i] = true;6        for (int p = 2; (long) p * p <= n; p++) {7            if (!isPrime[p]) continue;8            for (int m = p * p; m <= n; m += p) isPrime[m] = false;9        }10        return isPrime;11    }12 13    static List<Integer> primesUpTo(int n) {14        boolean[] isPrime = sieve(n);15        List<Integer> primes = new ArrayList<>();16        for (int i = 2; i <= n; i++) if (isPrime[i]) primes.add(i);17        return primes;18    }19}

(long) p * p <= n: p * p overflows an int once p > 46,340. p <= n / p is another safe way to write it.
boolean[] costs about one byte per number: 10⁷ numbers is about 10 MB. A BitSet stores one bit each (about 1.25 MB) at some speed cost.
The JDK uses the same idea: BigInteger.probablePrime sieves candidates with a java.math.BitSieve (odd numbers only) before running the expensive primality test.

Modular arithmetic

javaadd, sub, mul mod 10⁹+7java.math.BigInteger · java.util.*

1class Mod {2    static final int MOD = 1_000_000_007; // prime, and 2 * (MOD - 1) still fits in an int3 4    static int add(int a, int b) {5        return (a + b) % MOD;                      // a, b < MOD, so a + b < 2.15 * 10^9: no overflow6    }7 8    static int sub(int a, int b) {9        return ((a - b) % MOD + MOD) % MOD;        // Java's % can be negative: shift it back up10    }11 12    static int mul(int a, int b) {13        return (int) ((long) a * b % MOD);         // widen BEFORE multiplying: the product needs 60 bits14    }15 16    static int floorModDemo(int a, int m) {17        return Math.floorMod(a, m);                // library version of ((a % m) + m) % m18    }19}

javaBigInteger.modPow / modInversejava.math.BigInteger · java.util.*

1class Library {2    static long modPow(long base, long exp, long mod) {3        return BigInteger.valueOf(base).modPow(BigInteger.valueOf(exp), BigInteger.valueOf(mod)).longValue();4    }5 6    static long modInverse(long a, long mod) {7        // Works for any mod with gcd(a, mod) = 1 (extended Euclid inside); throws ArithmeticException otherwise.8        return BigInteger.valueOf(a).modInverse(BigInteger.valueOf(mod)).longValue();9    }10}

(a * b) % M with int a and b multiplies in 32 bits and overflows before the %. Cast first: (long) a * b % M.
Java's % takes the sign of the left operand (JLS §15.17.3): -7 % 3 == -1. Math.floorMod(-7, 3) == 2.
BigInteger.modPow and modInverse are perfect for checking your answers; in an interview, write the loop.

Fast power and the modular inverse

javabinary exponentiationjava.math.BigInteger · java.util.*

1class FastPower {2    /** base^exp mod m by binary exponentiation: about 2 * log2(exp) multiplications. */3    static long modPow(long base, long exp, long mod) {4        long result = 1 % mod;5        base = ((base % mod) + mod) % mod;6        while (exp > 0) {7            if ((exp & 1) == 1) result = result * base % mod;8            base = base * base % mod;9            exp >>= 1;10        }11        return result;12    }13 14    /** Inverse of a modulo a PRIME p (Fermat): a^(p-2), valid when a % p != 0. */15    static long modInverse(long a, long p) {16        return modPow(a, p - 2, p);17    }18}

Keep result, base and mod as long. With mod ≤ 2³¹ − 1, every product of two residues is below 2⁶², so it fits.
1 % mod (not 1) makes mod = 1 return 0, and ((base % mod) + mod) % mod handles a negative base.
Fermat's inverse a^(p−2) needs a prime p and a % p != 0. For other moduli, use extended Euclid or BigInteger.modInverse.

Counting: Pascal's triangle

javac[n][r] table in longjava.math.BigInteger · java.util.*

1class Pascal {2    /** c[n][r] = nCr for every 0 <= r <= n <= rows. Exact in long up to n = 66. */3    static long[][] table(int rows) {4        long[][] c = new long[rows + 1][];5        for (int n = 0; n <= rows; n++) {6            c[n] = new long[n + 1];7            c[n][0] = c[n][n] = 1;8            for (int r = 1; r < n; r++) {9                c[n][r] = c[n - 1][r - 1] + c[n - 1][r];10            }11        }12        return c;13    }14}

Exact in long up to row 66: C(66, 33) = 7,219,428,434,016,265,740 fits, C(67, 33) does not.
Each row only needs the row above it, so one long[] updated from right to left also works (O(n) space).

Counting: nCr mod p for big n

javafactorials + inverse factorialsjava.math.BigInteger · java.util.*

1class BinomialMod {2    static final int MOD = 1_000_000_007;3    final long[] fact, invFact;4 5    /** Precompute n! and 1/n! mod p once: O(n + log p). Then every nCr is O(1). */6    BinomialMod(int maxN) {7        fact = new long[maxN + 1];8        invFact = new long[maxN + 1];9        fact[0] = 1;10        for (int i = 1; i <= maxN; i++) fact[i] = fact[i - 1] * i % MOD;11        invFact[maxN] = power(fact[maxN], MOD - 2);              // Fermat: a^(p-2) = 1/a12        for (int i = maxN; i > 0; i--) invFact[i - 1] = invFact[i] * i % MOD;13    }14 15    long nCr(int n, int r) {16        if (r < 0 || r > n) return 0;17        return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD; // n! / (r! (n-r)!)18    }19 20    private static long power(long base, long exp) {   // the same loop as modPow above21        long result = 1;22        base %= MOD;23        while (exp > 0) {24            if ((exp & 1) == 1) result = result * base % MOD;25            base = base * base % MOD;26            exp >>= 1;27        }28        return result;29    }30}

One Fermat inverse for invFact[maxN], then invFact[i − 1] = invFact[i] * i walks down for free.
Multiply in steps and reduce each time: fact[n] * invFact[r] % MOD * invFact[n − r] % MOD.

Digits: arithmetic vs strings

java% 10 and / 10java.util.*

1class Arithmetic {2    /** Sum of the decimal digits. Works for negatives too: the sign is ignored. */3    static int digitSum(int x) {4        int sum = 0;5        while (x != 0) {6            sum += Math.abs(x % 10);   // last digit (Java's % keeps the sign of x, so take abs)7            x /= 10;                   // drop the last digit8        }9        return sum;10    }11 12    /** How many digits a non-negative number has (0 has one digit). */13    static int countDigits(long x) {14        int count = 1;15        while (x >= 10) {16            x /= 10;17            count++;18        }19        return count;20    }21 22    /** Digits of a non-negative number, most significant first. */23    static int[] toDigits(long x) {24        int[] digits = new int[countDigits(x)];25        for (int i = digits.length - 1; i >= 0; i--) {26            digits[i] = (int) (x % 10);27            x /= 10;28        }29        return digits;30    }31 32    /** Rebuild a number from its digits: shift left one place (x 10), then add the new digit. */33    static long fromDigits(int[] digits) {34        long x = 0;35        for (int d : digits) x = x * 10 + d;36        return x;37    }38}

javavia Long.toStringjava.util.*

1class ViaStrings {2    static int digitSum(int x) {3        int sum = 0;4        for (char ch : Long.toString(Math.abs((long) x)).toCharArray()) sum += ch - '0'; // '7' - '0' = 75        return sum;6    }7 8    static int countDigits(long x) {9        return Long.toString(x).length(); // allocates a String every call10    }11 12    static long reverse(long x) {13        return Long.parseLong(new StringBuilder(Long.toString(x)).reverse().toString());14    }15}

Arithmetic is O(digits) with no allocation; the String route is also O(digits) but creates objects every call.
Math.abs(Integer.MIN_VALUE) is still −2,147,483,648. Widen to long first, or work with negative values like the JDK does.
ch - '0' turns a digit character into its value: '7' - '0' == 7.

Java API you will actually use
call	does	cost
`Math.floorMod(x, m)`	Remainder in [0, m) for m > 0, even when x is negative	O(1)
`Math.multiplyExact(a, b) / Math.addExact(a, b)`	Throws ArithmeticException on int/long overflow instead of wrapping	O(1)
`Integer.MAX_VALUE / Long.MAX_VALUE`	2,147,483,647 and 9,223,372,036,854,775,807	—
`Math.abs(x)`	Absolute value. Careful: Math.abs(Integer.MIN_VALUE) stays negative	O(1)
`BigInteger.valueOf(a).gcd(BigInteger.valueOf(b))`	gcd for numbers of any size	Euclid + binary GCD
`BigInteger.valueOf(a).modPow(e, m)`	aᵉ mod m with arbitrary-size numbers	O(log e) multiplications
`BigInteger.valueOf(a).modInverse(m)`	a⁻¹ mod m for any m with gcd(a, m) = 1; throws otherwise	Extended Euclid
`new Random().nextInt(bound)`	Uniform int in [0, bound); rejects a few raw values to avoid modulo bias	O(1) expected
`Arrays.binarySearch(sorted, key)`	Index of key, or −(insertion point) − 1 when missing	O(log n)
`Long.toString(x) / ch - '0'`	Digits as text / one digit character to its value	O(digits) / O(1)

gcd or lcm of two numbers

→ Euclid's loop

O(log min(a, b)), no imports, four lines.

Is this one number prime?

→ Trial division up to √n

O(√n) and no memory; a sieve would be overkill.

Primes (or prime checks) for every number up to ~10⁷

→ Sieve of Eratosthenes

O(n log log n) once, then O(1) per lookup.

"Return the answer modulo 10⁹+7"

→ long products, reduce after every + and ×

Keeps every value below 10⁹+7 with no overflow.

aᵇ mod m, or division under a prime modulus

→ Fast power; inverse = a^(p−2)

O(log b) instead of O(b).

nCr for n ≤ 66 exactly, or small n mod p

→ Pascal's table

Only additions, easy to get right.

nCr mod p for n up to 10⁵ or more

→ fact[] and invFact[] tables

O(n) precompute, O(1) per query.

Pick an index with probability ∝ weight

→ Prefix sums + binary search

O(n) build, O(log n) per pick, O(n) memory.

07 · recognise

Spot the pattern

"The answer may be large, return it modulo 10⁹+7"

Reduce after every + and ×, use long for products, divide with Fermat's inverse

Fractions, slopes or ratios that must compare exactly

Reduce (dy, dx) by their gcd with one sign rule — never use doubles as keys

Count primes, or smallest prime factors for many numbers

Sieve once up to the limit

xⁿ with n up to 10⁹ or 10¹⁸

Fast power: square and multiply, O(log n)

"How many ways to choose / arrange"

nCr: Pascal's rule, or factorials with inverse factorials mod p

Reverse, palindrome or digit sums of a number, "without converting to a string"

Peel digits with % 10 and / 10; guard overflow before rev * 10

"Pick with probability proportional to weight"

Prefix sums + binary search for the first prefix ≥ ticket

Trailing zeros of n!

Count the factors of 5: n/5 + n/25 + n/125 + …

08 · traps & tricks

Mistakes to avoid, tricks to use

traps

(a * b) % M with ints: the product overflows before the % runs. Write (long) a * b % M.
Forgetting that Java's % can be negative: (a - b) % M may be below 0. Add M and take % again, or use Math.floorMod.
p * p <= n in the sieve overflows for p > 46,340 — use (long) p * p <= n.
Math.abs(Integer.MIN_VALUE) is still negative, and -Integer.MIN_VALUE == Integer.MIN_VALUE.
Checking for overflow after rev * 10 + d: by then the value has already wrapped around. Check before.
Using a double slope as a HashMap key: 0.0 and -0.0 are different keys, and vertical lines divide by zero.
lcm = a * b / gcd(a, b) overflows even when the lcm fits. Divide first: a / gcd * b.
Using Fermat's inverse with a modulus that is not prime, or with a ≡ 0 (mod p): the result is simply wrong.

tricks

Memorise three numbers: 2³¹ − 1 = 2,147,483,647 (int), about 9.2·10¹⁸ (long), and 10⁹+7.
When the statement says "modulo 10⁹+7", say out loud: "I'll keep everything reduced and use long for products." It shows you know the trap.
Before coding a digit loop, dry-run 120 on paper. Chalo, pop 0, then 2, then 1: rev = 21 — the trailing zero vanished by itself.
Test every number problem with 0, a negative, 1, Integer.MAX_VALUE and Integer.MIN_VALUE. Most hidden test cases live there.
If you forget the gcd loop under pressure, rebuild it from one fact: a common divisor of a and b also divides a % b.

09 · why & how

Questions you might be too shy to ask

Why do so many problems say "return the answer modulo 10⁹+7"?

Because the true answer is astronomically large — 2¹⁰⁰ alone has 31 digits and a long holds 19. The judge needs a fixed-size number to compare. 10⁹+7 is prime, a residue fits in an int, and (10⁹+6)² ≈ 10¹⁸ still fits in a long, so (long) a * b % M is always safe.

Can't I just compute the full answer and take % M once at the end?

No: the full answer is exactly the number that doesn't fit, so it overflows long before the end. The good news: % can be applied after every step without changing the final result. (a + b) % M = ((a % M) + (b % M)) % M, and the same holds for ×. So reduce after every + and ×, and every value stays below M.

In (long) a * b % M, which part happens first?

The cast binds tightest, so a becomes a long first. Then * and % run left to right: ((long) a * b) % M. The multiply happens in 64 bits, so no overflow. (long) (a * b) % M is wrong: the brackets make a * b run in 32 bits and overflow before the cast.

Why does Java say -7 % 3 is -1 and not 2?

Java's integer division truncates toward zero, so the remainder takes the sign of the left operand (JLS §15.17.3). Mathematically both −1 and 2 are "−7 mod 3"; Java picks −1. When you need 0..m−1, use Math.floorMod(x, m) or ((x % m) + m) % m.

Why not just write Math.pow(a, e) % M?

Math.pow returns a double. A double holds every whole number exactly only up to 2⁵³ ≈ 9·10¹⁵. 3⁴⁰ ≈ 1.2·10¹⁹ is already past that, so its last digits are lost, and % M then gives a wrong answer. Bigger powers even become Infinity. Use fast power with long and % M at every step.

Do I need to prove Euclid's algorithm in an interview?

One sentence is enough: a % b = a − q·b, so any number dividing a and b also divides a % b, and any number dividing b and a % b also divides a. Same common divisors, so the same gcd. Bas itna yaad rakho.

How do I divide when everything is mod p?

You multiply by the inverse instead. When p is prime and a % p ≠ 0, Fermat's little theorem gives a^(p−1) ≡ 1, so a^(p−2) is a's inverse — one fast power. For a modulus that isn't prime, use extended Euclid or BigInteger.modInverse; there the inverse exists only when gcd(a, m) = 1.

Is 1 a prime? Is 0?

Neither. A prime has exactly two different positive divisors: 1 and itself. 1 has only one divisor, and 0 is divisible by everything. That's why the sieve and the prime count start from 2, and why Count Primes returns 0 for n = 0, 1 and 2.

Sieve or trial division — how do I choose?

A few numbers: trial division up to √n each, no memory. Many queries up to a limit N (≈10⁷ fits in memory): sieve once in O(N log log N), then each lookup is O(1).

Palindrome Number: why does x == half / 10 handle odd lengths?

Dry-run 12321. The loop moves digits until half catches up: it stops with x = 12 and half = 123. The middle digit 3 sits at the end of half, and it doesn't need a partner. half / 10 drops it: 123 / 10 = 12, which equals x, so it's a palindrome. For even lengths (1221) the halves match directly: x = 12, half = 12.

Reverse Integer: do I need a special case for negative x?

No. In Java, -123 % 10 is −3 and -123 / 10 is −12, so the digits come out negative. The loop builds rev = −3 → −32 → −321 by itself. It's also safer than calling Math.abs(x) on the int first: Math.abs(Integer.MIN_VALUE) is still negative (it overflows).

Reverse Integer: where do the pop > 7 and pop < -8 checks come from?

From the last digits of the limits: Integer.MAX_VALUE is 2,147,483,647 and Integer.MIN_VALUE is −2,147,483,648. If rev is exactly 214,748,364, then rev * 10 is 2,147,483,640 — only a pop of 0..7 still fits. On the negative side, only −8..0 fit. Bas itna yaad rakho: 7 for MAX, −8 for MIN.

What if the items arrive as a stream and I can't build prefix sums?

Reservoir sampling, for a uniform pick. Keep one current choice. When the i-th item arrives (counting from 1), replace your choice with it with probability 1/i. At the end every one of the n items was kept with probability 1/n. That is LC 382 Linked List Random Node and LC 398 Random Pick Index.

Is Math.random() fine, or should I use Random?

Both are fine on LeetCode. random.nextInt(bound) reads more clearly and returns an int in [0, bound) with (approximately) equal chances: the JDK rejects a few raw values so no number is favoured (see the Random.nextInt Javadoc). (int) (Math.random() * bound) works too, with a tiny rounding bias you can ignore here.

10 · practice

Interview problems

Every problem has brute → better → optimal solutions in Java, with complexity and a dry run. show patterns & complexity

#66
Plus One
EasyIntuitGoogleAmazonMicrosoft
#9
Palindrome Number
EasyTCSInfosysBloombergGoogleMicrosoft+1
#202
Happy Number
EasyAirbnbGoogleAmazonApple
#7
Reverse Integermust-do
MediumBloombergAppleGoogleMicrosoftAmazon+1
#172
Factorial Trailing Zeroes
MediumBloombergMicrosoftAmazon
#204
Count Primes
MediumMicrosoftAmazon
#43
Multiply Stringsmust-do
MediumMetaMicrosoftGoogleAmazon
#528
Random Pick with Weightmust-do
MediumMetaUberLinkedInAmazonGoogle
#149
Max Points on a Line
HardLinkedInAppleGoogleAmazonMicrosoft

Also practise this here

Each problem has one home page in the course; these use this chapter's idea too. The note says what to look for.

#50
Pow(x, n)
Mediumin Recursion
Fast power on doubles, with negative n and the Integer.MIN_VALUE trap — the same halving idea as modPow.
#62
Unique Paths
Mediumin Dynamic Programming
The DP answer equals C(m + n − 2, m − 1): one nCr counts every path.
#268
Missing Number
Easyin Bits
A closed-form shortcut: Gauss's sum n(n + 1)/2 minus the array's sum.

11 · revise

The whole chapter on one screen

9 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

what it is
Interview number theory is five tools — gcd, the sieve, % M, fast power, nCr — plus digit peeling with % 10 and / 10.
template
Euclid: while (b != 0) { int r = a % b; a = b; b = r; } return a; — O(log min(a, b)).
template
Fast power: if ((e & 1) == 1) r = r * b % m; b = b * b % m; e >>= 1; — O(log e) steps.
use it when
"Modulo 10⁹+7" → reduce after every + and ×, long for products, divide by multiplying with a^(p−2).
cost
Sieve up to n: O(n log log n) time, O(n) memory. One number: trial division to √n, O(1) memory.
trap
(a * b) % M with ints overflows before the %. Write (long) a * b % M.
trap
Java's % keeps the left operand's sign: -7 % 3 == -1. Use Math.floorMod or ((x % m) + m) % m.
pro tip
Digit loops: guard rev > MAX / 10 before rev * 10 + d. Test 0, negatives and Integer.MIN_VALUE.
use it when
Weighted random → prefix sums + binary search for the first prefix[i] ≥ ticket.

12 · recall

Flip, remember, repeat

card 1 / 15

recall

Why is gcd(a, b) = gcd(b, a % b)?

tap or Space to flip ↻

Question 1: Why is gcd(a, b) = gcd(b, a % b)?

13 · check yourself

Quick quiz

What is gcd(1071, 462)?
a and b are ints below 10⁹+7. What's wrong with `return (a * b) % MOD;`?
In Java, what is -7 % 3?
In the sieve, why can prime p start crossing out at p² instead of 2p?
Fast power computes 2^e mod m with e = 10¹⁸. Roughly how many multiplications at most?
What is the inverse of 2 modulo 10⁹+7?
How many trailing zeros does 100! have?

0/0 correct · 7 left

14 · learn more