L47 · Math & Number Theory

Series: LeetCode — From Basics to Interview-Ready · Session 47 / 65 · Phase 3 · Advanced & specialised

Why this session exists

Fast power and the sieve show up often enough to be worth memorising. That is a narrow claim and I want to keep it narrow — this is not a number theory course, and most of number theory does not appear in interviews. What does appear is a small set of routines that are each under fifteen lines and each solve a family of problems outright.

There are four. Exponentiation by squaring, because any problem with "compute x^n" or "modulo 10^9+7" needs it and the naive loop is too slow. The sieve of Eratosthenes, because counting or enumerating primes below a bound has exactly one right answer. Euclid's algorithm for GCD, because it is three lines and it underpins fraction reduction, LCM, and a surprising number of grid and cycle problems. And binary search on an integer answer, because Sqrt(x) is really a search problem wearing a math costume.

Memorising these is genuinely the right strategy, which is unusual advice in this series. Elsewhere I have pushed derivation over recall, because patterns generalise and memorised solutions do not. Here the routines are small, exact, and unchanging. There is no insight to derive at the whiteboard that you would not simply be re-deriving from the same two lines every time. Learn them, verify you can write them cold, and spend your thinking budget elsewhere.

The meta-skill worth extracting is different: recognising when a problem is secretly a math problem. Happy Number looks like arithmetic and is actually cycle detection. Sqrt looks like math and is actually binary search. Count Primes looks like a loop and is actually a memory-access pattern. Reading past the surface is what this session trains.

Blank-file warm-up

Five minutes, empty file, no notes. Write fast exponentiation by squaring:

1. The iterative form with a while n: loop.
2. The three lines inside: conditional multiply, square the base, halve the exponent.
3. The handling for a negative exponent.

If the loop body comes out in the wrong order — squaring before the conditional multiply — the result is off by one factor of the base. Trace x^3 by hand to check.

Pattern anatomy

There is no single template here. There are four, and each has its own trigger. I will give all four and be explicit about the shape each one answers.

Fast power — the shape is "compute x^n where n is large". The invariant: at every step, result × base^n equals the original x^N. Halving n and squaring base preserves that product, and peeling off a factor when n is odd keeps it exact.

def fast_pow(x: float, n: int) -> float:
    if n < 0:
        x, n = 1 / x, -n
    result = 1.0
    while n:
        if n & 1:            # odd exponent: peel one factor into the result
            result *= x
        x *= x               # square the base
        n >>= 1              # halve the exponent
    return result
 
def pow_mod(base: int, exp: int, mod: int) -> int:
    """Same routine under a modulus — the version you actually need more often."""
    result = 1
    base %= mod
    while exp:
        if exp & 1:
            result = result * base % mod
        base = base * base % mod
        exp >>= 1
    return result

Sieve of Eratosthenes — the shape is "how many primes below n" or "give me all primes below n". The invariant: when the outer loop reaches p, every composite with a prime factor smaller than p has already been marked, so if p is still unmarked it is prime.

def count_primes(n: int) -> int:
    if n < 3:
        return 0
    is_prime = bytearray([1]) * n
    is_prime[0] = is_prime[1] = 0
    p = 2
    while p * p < n:
        if is_prime[p]:
            # start at p*p: smaller multiples already marked by smaller primes
            is_prime[p * p : n : p] = bytearray(len(range(p * p, n, p)))
        p += 1
    return sum(is_prime)

Two optimisations are load-bearing rather than decorative. Starting the inner marking at p * p rather than 2p is correct because any multiple kp with k < p has a prime factor below p and was already struck. Stopping the outer loop at p * p >= n is correct because a composite below n must have a factor at most its square root.

Euclid's GCD — the shape is any question about common divisors, fraction reduction, or periodicity.

def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return a
 
def lcm(a: int, b: int) -> int:
    return a // gcd(a, b) * b        # divide first: avoids overflow in fixed-width languages

Integer binary search — the shape is "find the largest k such that some monotone predicate holds". Sqrt is exactly this.

def my_sqrt(x: int) -> int:
    lo, hi = 0, x
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= x:
            lo = mid + 1          # mid is feasible; look higher
        else:
            hi = mid - 1
    return hi                     # hi ends at the largest feasible value

The cue

You are looking at a math problem when the statement contains these tells:

1. "Modulo 10^9 + 7" — this is a counting problem whose answer overflows, and somewhere in it you will need modular arithmetic and quite possibly modular exponentiation. The specific constant is a large prime, chosen so that modular inverses exist for everything you care about.
2. "Compute x^n" with n up to 10^9 or beyond. Naive multiplication is O(n) and hopeless. Fast power is O(log n) and mandatory.
3. "Primes below n" with n up to 10^6 or 10^7. Sieve. Trial division per number is O(n·sqrt(n)) and will not finish.
4. Fractions, ratios, "reduce to lowest terms", or anything about repeating cycles. GCD, almost always.
5. "Without using the built-in function" — sqrt, pow, division. The problem is asking you to reimplement a primitive, and the intended method is binary search or bit-shifting.
6. A digit-manipulation loop that might not terminate — sum of squared digits, digital roots. If a process can cycle, the answer involves cycle detection rather than arithmetic.

Tell 1 is worth extra attention. 10^9 + 7 appearing anywhere means every arithmetic operation in your solution should be reduced modulo it as you go, not at the end. Reducing at the end is a bug in fixed-width languages and merely slow in Python.

Guided solve

Pow(x, n) — implement pow(x, n) computing x raised to the power n, where n can be negative and as large as 2^31 in magnitude.

Naive first, and name why it fails. Multiplying x by itself n times is O(n). With n around two billion that is two billion multiplications and it will not complete. So you need something logarithmic, and the route to logarithmic is halving.

The observation is that x^n can be built from x^(n/2). If n is even, x^n = (x^(n/2))^2 — one squaring instead of n/2 multiplications. If n is odd, x^n = x · (x^((n-1)/2))^2. Each step halves the exponent, so there are log2(n) steps, about 31 for a 32-bit exponent.

The iterative form reverses this into a sweep over the bits of n. Think of it as: n in binary tells you which powers x^1, x^2, x^4, x^8, ... to multiply together. Bit i of n set means include x^(2^i). The loop maintains x as the current x^(2^i), squaring it each iteration to advance i, and multiplies it into the result whenever the corresponding bit is set.

Trace x = 2, n = 10. Binary 10 is 1010, so the answer is 2^2 × 2^8 = 4 × 256 = 1024. The loop: n=10 even, square x to 4, n becomes 5. n=5 odd, result = 4, square x to 16, n becomes 2. n=2 even, square x to 256, n becomes 1. n=1 odd, result = 4 × 256 = 1024, n becomes 0. Loop ends. Correct.

Now the edge cases, which is where this problem actually gets you:

Negative exponent. x^(-n) = 1 / x^n. Handle it by inverting x and negating n at the top, which is what the template does. The alternative — computing the positive power and inverting at the end — is equivalent but loses a little floating-point precision.

n = -2^31. Negating it overflows a 32-bit signed integer in Java or C++, since 2^31 is not representable. Python is immune because its integers are unbounded, but the interviewer may well ask, and the answer is to widen to a 64-bit type before negating.

x = 0 with negative n. Division by zero. The problem constraints usually exclude it; check and say so rather than silently assuming.

Floating-point accumulation. Repeated squaring compounds rounding error, so pow(2.0, 10) might come out as 1023.9999999999998 rather than exactly 1024. For the float version this is accepted within tolerance. For the modular integer version it does not arise at all, which is one more reason the modular variant is the cleaner thing to practise.

Solo timed

Fifteen minutes each, timer running, no editorial until it fires.

• Sqrt(x) — integer square root, no built-in. Binary search on the answer. The trap is the return value: decide before you code whether you return lo, hi, or mid, and justify it from the loop invariant.
• Count Primes — sieve. Get both optimisations right: inner loop starts at p*p, outer loop stops at p*p >= n.
• Happy Number — repeatedly replace the number by the sum of the squares of its digits; decide whether it reaches 1. This is cycle detection. Floyd's tortoise and hare gives O(1) space; a seen-set gives O(k) space and is easier to write.

If those land early, do Excel Sheet Column Title — base conversion with a one-indexed alphabet, which is a small but genuinely fiddly off-by-one exercise.

Common failure modes

Squaring before the conditional multiply. The order inside the fast-power loop matters: test the bit and multiply into the result first, then square the base. Reversed, you get x^(n+1) or worse. Trace x^1 — it should return x and a reversed loop returns x^2.

Sieve inner loop starting at 2p. Not wrong, just wasteful — it re-marks composites already struck by smaller primes. On n = 10^6 the difference is measurable. Start at p*p.

Sieve outer loop running to n instead of to sqrt(n). Also not wrong, also wasteful. Once p exceeds the square root, every remaining unmarked number is prime and there is nothing left to mark.

Off-by-one on the binary search return. With the lo <= hi loop form, hi ends at the largest value satisfying the predicate and lo at the smallest violating it. Know which one you want. Test with x = 8, where the answer is 2, and x = 1, where it is 1.

Modular arithmetic applied only at the end. In fixed-width languages the intermediate product overflows long before you get there. Reduce after every multiplication. In Python it is not a correctness bug but the integers grow huge and it becomes slow.

Assuming % on negatives matches other languages. Python's % returns a result with the sign of the divisor, so -7 % 3 is 2, while C and Java give -1. If you are translating a solution across languages, this bites.

Complexity

Fast power: O(log n) time, O(1) space in the iterative form. The exponent halves every iteration, so the loop runs floor(log2(n)) + 1 times — at most 31 for a 32-bit exponent. The recursive form is the same time but O(log n) stack space.

Sieve: O(n log log n) time, O(n) space. The time bound comes from summing n/p over all primes p below n, and the sum of prime reciprocals grows like log log n. That is close enough to linear that you can treat it as linear for estimation. Space is one byte per candidate with a bytearray, so n = 10^7 is ten megabytes — fine. A bitset would be eight times smaller if you need it.

GCD: O(log(min(a, b))) by Euclid's algorithm. Each modulo step at least halves the smaller argument within two iterations, which is where the logarithm comes from.

Integer binary search: O(log range) — for Sqrt(x) with x up to 2^31, that is about 31 iterations of one multiplication each.

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

These four routines are the rare case where pure recall is the goal. If any of them takes more than three minutes to write cold, it belongs at failed regardless of whether you eventually produced it.