Math Algorithms: Complete Guide with Worked Examples

Math algorithm questions show up in interviews more often than candidates expect. The hard math is rare. Nearly every question reduces to one of a few primitives, mostly greatest common divisor, prime checks, and fast exponentiation. Learn those three well and the rest of the category becomes pattern matching.

Definition: the math algorithms pattern is the practice of recognizing which number-theory primitive a problem needs, then applying it instead of brute force. The payoff is usually large. A naive prime check scans up to the number itself. A careful one scans to its square root. Repeated multiplication for an exponent takes N steps. Squaring takes about log2(N).

Real-World Analogy

Suppose you have a rectangular floor that is 48 by 18 units and you want to cover it with the largest square tiles you can, with no cutting. Try a tile of 18. One fits, and a 12 by 18 strip remains. Try 12. One fits, and a 6 by 12 strip remains. Try 6. It covers the rest. The answer is 6, and 6 is the greatest common divisor of 48 and 18.

Watch what happens between attempts. Each leftover strip becomes the new rectangle, and the same move repeats until the strip is square. That is the Euclidean algorithm in physical form. The floor never needs a ruler, and the problem never needs a loop over all possible tile sizes.

Visual Explanation

The Euclidean algorithm replaces the larger of two numbers with the remainder of dividing it by the smaller one, and repeats.

    graph TD
    A["GCD(48, 18)"] --> B["48 mod 18 = 12, so GCD(18, 12)"]
    B --> C["18 mod 12 = 6, so GCD(12, 6)"]
    C --> D["12 mod 6 = 0, so GCD(6, 0)"]
    D --> E["Answer: 6"]
  

Two things make this fast. The pair shrinks quickly, because a remainder is always smaller than the divisor it came from. And the loop stops the moment a remainder hits zero, because the previous divisor then divides both numbers exactly. The last nonzero remainder is the GCD.

Fast exponentiation follows the same “shrink the problem” logic, but with the exponent instead of the numbers. For 2^13, write 13 in binary as 1101. The ones tell you which powers to multiply. For 2^13 that means 2^8 * 2^4 * 2^1. Compute 2, 4, 16, 256 by repeated squaring, keep the powers that match the set bits, and multiply them. Four squarings replace twelve multiplications, and the gap grows with the exponent.

When to Use This Pattern

• The problem mentions divisibility, factors, or common divisors. Phrasing like “divisible by both”, “share a factor”, or “greatest common divisor” is the clearest signal.
• You must compute a very large power. If a loop that multiplies N times will not fit the time limit, exponentiation by squaring is the intended tool.
• The input is a number and the naive approach iterates from 1 up to it. An O(N) loop over a 10^9 input does not finish, so a formula or a math shortcut is expected.
• Results must be returned modulo a prime like 10^9 + 7. That phrasing almost always means modular arithmetic and fast exponentiation are part of the plan.
• You need all primes up to a bound, or you will answer many prime checks in one problem. The sieve beats repeated trial division here.

Complexity Analysis

The GCD is logarithmic because the worst case behaves like consecutive Fibonacci numbers, which shrink by a constant ratio at every step. Fast exponentiation halves the exponent each iteration, so an exponent of 10^9 takes about 30 squarings. The sieve is the only primitive that pays real memory, and it buys near-constant prime checks afterward.

Common Mistakes

Overflow before the check. In digit and power problems the dangerous step is the multiply. Once a value has overflowed, the check is too late. Test the condition before you append a digit, and apply the modulo after every multiply. In languages with fixed-width integers, intermediate products also need a wider type.

Scanning to N when sqrt(N) is enough. Factors come in pairs, i and N/i. A composite number always has a factor at or below sqrt(N), so loops that run to N waste most of their work. This shows up in prime checks, divisor sums, and perfect-number tests.

Assuming every language floors its modulo. In Python and Ruby, -123 % 10 is 7. In Java, C++, Go, and JavaScript it is -3. Digit-extraction loops that work in one family silently corrupt negative inputs in the other. Handle the sign explicitly.

Forgetting the sieve edges. The sieve must mark 0 and 1 as not prime, and the inner loop starts at i*i because smaller multiples were already marked by smaller primes. Boundary questions like “less than n” also decide whether n itself counts.

Related Patterns

• Bit Manipulation . Bit tricks are the low-level layer under many math shortcuts, from parity checks to powers of two.
• Divide and Conquer . Fast exponentiation is a textbook divide-and-conquer. Split the exponent in half, solve the halves, and combine with one multiply.
• Binary Search . When a math problem asks for a value with a monotonic condition, like a square root or a coin count, binary search over the answer space is the tool.

Next Steps

The math primitives are short, which means recall matters more than comprehension. The code templates cover all three primitives in 6 languages. The practice problems start with digit manipulation and end with modular exponentiation against an exponent too large for any integer type.