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:
ddividesaifa % d == 0(no remainder). 12 divides 48. - GCD (greatest common divisor): the biggest number that divides both
aandb.gcd(48, 36) = 12. Every number divides 0, sogcd(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), untilb = 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
dwhiled * 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 along(max ≈ 9.2 × 10¹⁸).- Fast power (binary exponentiation, exponentiation by squaring): compute
a^bin O(log b) steps by squaringaand halvingb. b & 1: the last bit ofb(1 ifbis odd).b >>= 1: shift right, i.e. drop the last bit (halveb).- Modular inverse: the number
xwitha * x % m == 1, the "division" of modular arithmetic. Whenmis 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.
- Mark every number from 2 to n as "not crossed".
- For
i = 2, 3, ...whilei * i <= n: ifiis not crossed, it is prime; crossi*i, i*i + i, i*i + 2i, .... - Start at
i * i: every smaller multiplek·iwithk < iwas already crossed by the smaller prime factor ofk. - 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
- Why does
gcd(a, b) = gcd(b, a % b)hold? Any common divisor ofaandbdividesa − q·b = a % b, and any common divisor ofbanda % bdividesa. Same set of common divisors, same greatest one. - How many steps does Euclid take? O(log min(a, b)); the worst case is two consecutive Fibonacci numbers.
- Why does the sieve start crossing at
i * i? Every smaller multiplek·i(k < i) has a prime factor smaller thani, so it is already crossed. - Complexity of the sieve? O(n log log n) time, O(n) space.
- How do you test one big number for primality? Trial division up to √x, O(√x); for 64-bit numbers, Miller–Rabin.
- 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).
- Why mod 1e9+7? It is prime (inverses exist) and the product of two remainders fits in a 64-bit integer.
- 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, whengcd(a, m) = 1. - How do you handle negative numbers with
%in Java?((x % m) + m) % m, orMath.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 * iin O(n log log n). Keepi * iin along. - Huge answers: work mod 1e9+7, taking
% MODafter every multiplication; after a subtraction, addMODbefore 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.