← Math & Numbers · guided lesson
Math & Number Theory
the story
Euclid's algorithm (gcd and lcm)
Every tool here exists because something was too slow or broke without it. Here is what.
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 solved
Find the largest number that divides two numbers exactly — without listing all their divisors.
why it matters: without it
Exact fractions would need slow divisor searches, and RSA key setup (which needs a modular inverse) would lose its fast path.
sources: Euclid's Elements, Book VII, Proposition 2 (D. E. Joyce, Clark University) ↗ · Euclidean algorithm — history and Lamé's bound ↗ · D. E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, §4.5.2 ↗
also in this chapter: Sieve of Eratosthenes · Modular arithmetic (and why 10⁹+7) · Fast power (binary exponentiation) · Combinations nCr and Pascal's triangle (Meru-prastāra) · Place-value digits (% 10 and / 10) · Weighted random pick (prefix sums + binary search)
the idea
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.
watch it
Euclid's gcd step by step
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
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.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
watch it
Sieve of Eratosthenes on a number board
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Sieve of Eratosthenes on a number board
Each prime crosses out its multiples starting at p². Whatever survives is prime.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
key idea 1 of 8
Read it once. Say it out loud once. Bas.
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).
key idea 2 of 8
Read it once. Say it out loud once. Bas.
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.
key idea 3 of 8
Read it once. Say it out loud once. Bas.
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.
key idea 4 of 8
Read it once. Say it out loud once. Bas.
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.
key idea 5 of 8
Read it once. Say it out loud once. Bas.
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.
key idea 6 of 8
Read it once. Say it out loud once. Bas.
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.
key idea 7 of 8
Read it once. Say it out loud once. Bas.
Digits: x % 10 reads the last digit, x / 10 drops it, rev * 10 + d appends one. Guard against overflow before the multiply.
key idea 8 of 8
Read it once. Say it out loud once. Bas.
Weighted random: prefix sums turn weights into ticket ranges; a binary search finds the owner of a random ticket in O(log n).
spot the pattern
When you see this, think this
"The answer may be large, return it modulo 10⁹+7"
Reduce after every + and ×, use
longfor products, divide with Fermat's inverseFractions, 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)
+4 more signals on the chapter page
watch out
A trap or two
Many wrong answers in interviews come from small slips like these, not from the hard part.
(a * b) % Mwithints: the product overflows before the%runs. Write(long) a * b % M.- Forgetting that Java's
%can be negative:(a - b) % Mmay be below 0. Add M and take%again, or useMath.floorMod.
quick check
One question. No pressure.
What is gcd(1071, 462)?
now try
Your first real problem
You know enough to try this one. Stuck? Use the hints; that is what they are for.
Reverse Integer
open the problem →recall
Flip a few cards
Answer in your head first, then flip. Grade yourself honestly; the schedule brings back what you forget.
Why is gcd(a, b) = gcd(b, a % b)?
Question 1: Why is gcd(a, b) = gcd(b, a % b)?
done
Lesson complete
Chalo, that is the core. The full chapter has the rest: cost tables, Java details and more problems.