Arithmetic essentials

For integers, a / b gives the quotient truncated toward zero and a % b the remainder, with a == (a / b) * b + a % b. Dividing by 10 removes the last digit and % 10 reads it, which is how you process digits.

Run the digit-sum animation: each step takes n % 10 and then n / 10.

1int n = 4072, s = 0;
2while (n > 0) { s += n % 10; n /= 10; }   // 2 + 7 + 0 + 4 = 13
3int q = 17 / 5, r = 17 % 5;                // q = 3, r = 2: 17 = 3*5 + 2

1static int sumDigits(int n) {
2    if (n == 0) return 0;               // no digits left
3    return n % 10 + sumDigits(n / 10);  // last digit + the rest
4}

The remainder (modulo) tells how far a number is past the last multiple of the divisor. It is used for parity (n % 2), cyclic indexes ((i + 1) % n), hashing and number theory. In Java the sign follows the dividend, so use Math.floorMod when a non-negative result is required.

Euclid's algorithm uses the identity gcd(a, b) = gcd(b, a mod b). Step through it below.

1int even = 10 % 2;                  // 0
2int next = (4 + 1) % 5;              // 0: wraps around a 5-element ring
3int prev = Math.floorMod(0 - 1, 5);  // 4
4int g = gcd(48, 18);                 // 6
5static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

1static int gcd(int a, int b) {
2    if (b == 0) return a;               // base case
3    return gcd(b, a % b);               // same answer, smaller numbers
4}

⌊x⌋ is the greatest integer ≤ x and ⌈x⌉ is the smallest integer ≥ x. For positive integers, ⌈a / b⌉ = (a + b - 1) / b, which avoids floating point. For negative numbers Java division truncates, so use Math.floorDiv for floors.

Binary search takes ⌊log₂ n⌋ + 1 probes at most, and merge sort recursion depth is ⌈log₂ n⌉.

1int pages = (10 + 3 - 1) / 3;            // ceil(10 / 3) = 4
2int f = Math.floorDiv(-7, 2);            // -4
3int c = -Math.floorDiv(-(-7), 2);        // ceil(-7 / 2) = -3
4double d = Math.ceil(10 / 3.0);          // 4.0

|x| is the distance from zero. In code it measures differences regardless of direction: Math.abs(a - b). The triangle inequality |a + b| ≤ |a| + |b| appears in Manhattan distance and in proofs.

Beware: Math.abs(Integer.MIN_VALUE) is negative, and Math.abs(a - b) can overflow for large operands. Compare with Integer.compare when you only need order.

1int manhattan = Math.abs(1 - 4) + Math.abs(2 - (-2));   // 3 + 4 = 7
2long safeDiff = Math.abs((long) a - b);                   // widen before subtracting

xⁿ is x multiplied n times; the n-th root undoes it. Integer powers grow quickly: 2³¹ already exceeds int. Compute powers with a loop or binary exponentiation (about log₂ n multiplications) rather than Math.pow, which returns an inexact double.

Watch fast exponentiation square the base and halve the exponent.

1static long pow(long base, int exp, long mod) {
2    long result = 1; base %= mod;
3    while (exp > 0) {
4        if ((exp & 1) == 1) result = result * base % mod;
5        base = base * base % mod;
6        exp >>= 1;
7    }
8    return result;
9}
10static long isqrt(long n) {            // floor(sqrt(n)), safe up to Long.MAX_VALUE
11    if (n < 2) return n;
12    long r = (long) Math.sqrt((double) n);
13    while (r > n / r) r--;            // r * r > n, written without multiplying
14    while (r + 1 <= n / (r + 1)) r++; // (r + 1)^2 <= n
15    return r;
16}

1static long power(long x, int n) {
2    if (n == 0) return 1;                           // x^0 = 1
3    long half = power(x, n / 2);                    // solve a problem half the size
4    return (n % 2 == 0) ? half * half : half * half * x;
5}

log_b(n) is the exponent to which b must be raised to get n: log₂ 1024 = 10. Equivalently it counts how many times you can halve n before reaching 1. That is why binary search, balanced trees and heaps take O(log n).

Change the starting value in the animation and watch the number of halvings equal ⌊log₂ n⌋.

1int n = 1000, steps = 0;
2while (n > 1) { n /= 2; steps++; }       // steps = 9 = floor(log2(1000))
3int floorLog2 = 31 - Integer.numberOfLeadingZeros(1000);   // 9
4double ln = Math.log(1000) / Math.log(2);                  // 9.9657...

1static int halvings(int n) {                // = floor(log2 n) for n >= 1
2    int count = 0;
3    while (n > 1) {
4        n /= 2;                             // integer division
5        count++;
6    }
7    return count;
8}
9
10static int doublings(int n) {               // = ceil(log2 n)
11    int count = 0;
12    for (long x = 1; x < n; x *= 2) count++;
13    return count;
14}

Laws: xᵃ · xᵇ = xᵃ⁺ᵇ, (xᵃ)ᵇ = xᵃᵇ, x⁻ᵃ = 1/xᵃ, x⁰ = 1. Exponentials grow faster than any polynomial, and logarithms grow slower than any positive power. Hence 2ⁿ ≫ n² ≫ n log n ≫ n ≫ log n for large n.

Useful anchors: 2¹⁰ = 1,024 ≈ 10³, so 2²⁰ ≈ 10⁶ and 2³⁰ ≈ 10⁹.

n! = n · (n-1) · … · 1, with 0! = 1. It counts the orderings of n distinct items and grows faster than any exponential: 12! = 479,001,600 is the largest factorial in int, and 20! = 2,432,902,008,176,640,000 is the largest in long. 21! overflows long.

Algorithms that try all orderings are practical only up to about n = 10 or 11.

1long f = 1;
2for (int i = 2; i <= 20; i++) f *= i;     // 2432902008176640000
3// i = 21 would overflow: use BigInteger beyond 20!
4BigInteger big = BigInteger.ONE;
5for (int i = 2; i <= 30; i++) big = big.multiply(BigInteger.valueOf(i));

Scientific notation writes a value as m × 10ᵉ. It makes constraints and growth easy to compare: n ≤ 2 × 10⁵ means 200,000. Java accepts 1e9 (a double) and 1_000_000_000 (an int).

(int) 1e9 is 1,000,000,000, but 1e18 does not fit in int and needs (long) 1e18 or the literal 1_000_000_000_000_000_000L.