Math and Number Theory Pattern: Template + 485 LeetCode Problems

What the math and number theory pattern is

Some problems have no algorithm worth writing because they have a formula. The tell is a statement about digits, divisors, remainders, or counting arrangements, together with a constraint large enough — 10⁹ and up — that any loop over the input range is hopeless by construction. The recurring tools are small in number: the Euclidean algorithm for the greatest common divisor, which underlies fractions, cycles and repeating patterns; modular arithmetic, where addition and multiplication distribute over the modulus so you can reduce at every step instead of overflowing; a sieve when many primes below a bound are needed rather than one primality test; and fast exponentiation, which raises to the nth power in log n multiplications by squaring. The other half of this pattern is not a technique but a habit: compute the first six answers by hand, look for the pattern, then prove it. An invariant — a quantity the operations never change — usually collapses a simulation into a one-line check.

When to use it

• —The constraints are far too large to iterate, so the answer must be computed rather than searched.
• —The statement is about digits, divisibility, remainders, primes, or gcd.
• —You are counting arrangements and the answer is requested modulo 10⁹ + 7.
• —A simulation is described but some quantity is clearly conserved throughout it.

The math and number theory template in Python

The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 485 problems listed below.

def gcd(a, b):
    while b:
        a, b = b, a % b       # gcd(a, b) == gcd(b, a mod b), and b strictly shrinks
    return a

def power_mod(base, exponent, mod):
    result = 1
    base %= mod
    while exponent:
        if exponent & 1:                  # this bit of the exponent is set
            result = result * base % mod
        base = base * base % mod          # square for the next bit
        exponent >>= 1
    return result

Complexity characteristics

Time

O(log n) or O(1)

Auxiliary space

O(1)

The point of the pattern is that there is no loop over the input: a closed form is O(1), the Euclidean algorithm for a greatest common divisor is O(log min(a, b)), and fast exponentiation raises to the nth power in O(log n) multiplications. A sieve is the exception that costs real time and memory — O(n log log n) to build and O(n) to hold — and is only worth it when many primes below a bound are needed rather than a single primality test.

All 485 math and number theory LeetCode problems

Every problem in the library the math and number theory pattern applies to, grouped by LeetCode's own difficulty rating. 413 of the 485 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.

Related patterns

Problems sit in more than one pattern more often than not, and the overlap is where the interesting follow-up questions live.

Math and Number Theory pattern FAQ

More ways in: all 22 patterns, the curated study lists, or the full problem list.