LearnAbout

Math Utilities

On this page
Quick reference
GCD (Euclidean, mod version)O(log(min(a,b)))
Primality check (trial division)O(√n)
Modular exponentiation (fast power)O(log n)
Bit operations (AND/OR/XOR/shift)O(1)
The Idea

GCD (greatest common divisor) has a geometric picture worth keeping in your head: imagine a rectangle, say 18×12, and you want to tile it exactly with the biggest possible square, no gaps, no overhang. That biggest square's side length is GCD(18, 12) = 6. You can find it by repeatedly cutting the largest square you can off the rectangle and repeating on what's left — that's the same process as the Euclidean algorithm, just drawn instead of computed.

Modulo (%) is clock arithmetic. A 12-hour clock doesn't count 13, 14, 15 — it wraps back to 1, 2, 3. `13 % 12` is 1 for exactly that reason: modulo gives you the remainder after wrapping around every multiple of the divisor. It's the tool for anything cyclical — indexing into a fixed-size buffer, checking even/odd, spreading values evenly across buckets.

A prime number is one that can't be tiled evenly by any square smaller than itself (other than a 1×1 square) — no whole-number factors besides 1 and itself. Primes are the "atoms" of the integers: every whole number greater than 1 is either prime or built by multiplying primes together.

Underneath all of it, a computer only has two symbols: 0 and 1 — bits. Every number, character, and instruction is some pattern of bits, and operations like AND/OR/XOR/shift work directly on those patterns. They look low-level, but they're often the fastest tool available, because they map straight onto what the hardware already does.

These aren't separate tricks — they compose. Modular exponentiation combines fast power with modulo; primality checks lean on the same "factor pairs mirror around √n" idea that makes trial division efficient.
Build It
Core routines
// Euclidean GCD — subtraction intuition first, then the efficient form:
// GCD(a, b) == GCD(a - b, b) when a > b  (repeatedly subtracting the smaller from the larger
// eventually lands on the same answer as the tiling picture above)
// The efficient version replaces repeated subtraction with a single mod:
function gcd(a, b):
    while b != 0:
        a, b = b, a % b   // a % b does many subtractions in one step
    return a
isPrime — trial division, O(√n)
function isPrime(n):
    if n < 2:
        return false
    for i in range(2, int(sqrt(n)) + 1):   // factors always come in pairs that
        if n % i == 0:                      // straddle sqrt(n), so checking past
            return false                     // sqrt(n) can never find a new one
    return true
If n has a factor bigger than √n, it must pair with a factor smaller than √n — so if nothing up to √n divides n, nothing above √n can either.
modPow — fast modular exponentiation via repeated squaring, O(log n)
function modPow(base, exp, mod):
    result = 1
    base = base % mod
    while exp > 0:
        if exp % 2 == 1:              // odd exponent: fold in the current base
            result = (result * base) % mod
        exp = exp // 2                 // halve the exponent...
        base = (base * base) % mod    // ...and square the base to match
    return result
Naive exponentiation multiplies n times — O(n). Squaring the base and halving the exponent each step means you only do log₂(n) multiplications to reach the same power.
bit operations — AND / OR / XOR / shift, each O(1)
a & b    // AND: 1 only where BOTH bits are 1        — used to mask/check specific bits
a | b    // OR:  1 where EITHER bit is 1              — used to set specific bits
a ^ b    // XOR: 1 where the bits DIFFER               — a value XORed with itself is 0
a << k   // left shift: multiply by 2^k
a >> k   // right shift: divide by 2^k (integer division)

n & (n - 1)   // clears the lowest set bit — n-1 flips every trailing 0 to 1 and the
              // lowest 1 to 0, so ANDing with n turns that lowest 1 off
x ^ x == 0    // any value XORed with itself cancels to 0 — the trick behind "find the
              // one unpaired value" problems
Know It

Fixed-width integer operations (bit ops, basic arithmetic) are O(1) because a CPU register holds a bounded number of bits — the hardware does the work in one step regardless of the number's value. Everything below that assumption gets more expensive as the numbers involved grow.

OperationTimeSpaceWhy
GCD (Euclidean, mod version)O(log(min(a,b)))O(1)Each step replaces (a, b) with (b, a % b); the smaller value shrinks by at least half every two steps, so it takes a logarithmic number of steps to reach 0.
Primality check (trial division)O(√n)O(1)Only need to test candidate factors up to √n — anything past that would have already shown up paired with a smaller factor.
Modular exponentiation (fast power)O(log n)O(1)Squaring the base and halving the exponent each step reaches the answer in log₂(n) multiplications, versus O(n) for multiplying the base by itself n times naively.
Bit operations (AND/OR/XOR/shift)O(1)O(1)A fixed-width integer (32 or 64 bits) fits in a single CPU register — the operation touches all bits at once in hardware, independent of the number's value.
Break It

GCD of 0 and negatives

GCD(0, 0) or GCD with a negative argument

GCD(0, 0) is conventionally defined as 0 (no positive common divisor exists otherwise), and GCD(a, 0) = |a|. For negative inputs, GCD is defined via absolute value — GCD(-12, 18) = GCD(12, 18) = 6 — because divisibility doesn't care about sign, but a naive mod-based implementation can return a negative result if you don't normalize signs first.

0, 1, and negatives are never prime

checking primality of small or negative n

Primality requires exactly two distinct positive divisors: 1 and itself. 0 has infinitely many divisors, 1 has only one divisor (itself), and negative numbers aren't part of the standard definition at all — all three are "not prime" by definition, not by any calculation. A common bug is a trial-division loop that never runs for n < 2 and silently returns true.

Modulo of negative numbers isn't universal

either operand of % is negative

Python's `%` always returns a result with the same sign as the divisor (true mathematical mod) — `-7 % 3` is `2`. C, Java, and JavaScript's `%` follows the sign of the dividend instead (a truncating remainder) — `-7 % 3` is `-1` in those languages. Porting modulo-based logic (like circular buffer indexing) between languages without accounting for this is a classic silent bug.

Integer overflow and sign bits in shifting

shifting into or past the sign bit

Left-shifting a signed integer far enough can push a 1 into the sign bit, flipping a positive number negative in languages with fixed-width signed integers — and shifting a fixed-width type by more bits than it has is undefined or implementation-specific behavior in several languages. Bit tricks that work perfectly in a language with arbitrary-precision integers (like Python) can silently break when ported to a fixed-width language.

Use It
Greatest Common Divisor of Strings
Two strings share a 'divisor' string only if concatenating them both ways matches — then the answer's length is literally GCD(len(str1), len(str2)), computed with the Euclidean algorithm.
Easy
Count Primes
Trial-dividing every number up to n is too slow. The Sieve of Eratosthenes flips it: for each prime found, cross out all its multiples in one pass — the batch version of the same idea.
Medium
Power of Two
A power of two has exactly one bit set. `n & (n - 1) == 0` clears that one bit and checks nothing else remains — O(1), no loop needed.
Easy
Power of Three
No single-bit trick for base 3 — repeatedly divide by 3 while it divides evenly, then check you landed on exactly 1.
Easy
Single Number
XOR every element together. Every value that appears twice cancels itself out (x ^ x == 0); whatever survives is the unpaired one.
Easy
Number of 1 Bits
Repeatedly apply `n & (n - 1)` to strip the lowest set bit and count how many strips it takes to reach 0.
Easy
Reverse Bits
Walk all 32 bit positions: shift the result left to make room, pull off the lowest bit of n with `n & 1`, OR it in, then shift n right.
Easy
Add Digits
Repeated digit-summing until one digit remains has a closed-form shortcut: the answer is `1 + (n - 1) % 9` (with 0 handled separately) — digital roots cycle mod 9.
Easy
Excel Sheet Column Number
Treat the letters as base-26 digits (A=1..Z=26): result = result * 26 + digitValue, left to right — the same positional math as decimal, just base 26.
Easy
Happy Number
Repeatedly summing squared digits either reaches 1 or falls into a cycle. Detect the cycle with Floyd's slow/fast pointer — one pointer applies the digit-square-sum step once per round, the other applies it twice, and if they ever land on the same value there's a cycle. (Phase 2's Linked Lists topic reuses this exact slow/fast trick to detect cycles in a chain of nodes.)
Easy