Overview

You do not need advanced mathematics for most DSA, but a handful of number-theory tools show up constantly: computing a greatest common divisor, listing primes, working "modulo 10⁹+7" so numbers don't overflow, and raising numbers to huge powers quickly. Aptitude-style coding rounds in campus placements lean heavily on exactly these.

The common thread is efficiency. Checking primality by trial division up to n is O(n); up to √n it is O(√n); the Sieve of Eratosthenes finds every prime up to n in O(n log log n). Recognising which tool fits turns a timeout into an instant answer.

Key concepts

Tick a concept once you can explain it in your own words without notes.

Complexity cheat sheet

OperationCost
gcd(a, b)O(log min(a, b))
Primality by trial divisionO(√n)
Sieve up to nO(n log log n) time, O(n) space
Fast power aᵇ mod mO(log b)

Patterns to recognise

Reduce modulo at every step

Use it for: Answers "modulo 10⁹+7".

Apply % after every addition and multiplication, not only at the end, or intermediate values overflow.

Precompute with a sieve

Use it for: Many primality queries on numbers up to ~10⁷.

Build the sieve once, then answer each query in O(1).

Count factors, not products

Use it for: Trailing zeros, divisibility of factorials.

Trailing zeros of n! = number of factors of 5 in 1..n, because factors of 2 are always more plentiful.

Code template

GCD, sieve and modular fast power
MOD = 10**9 + 7


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def sieve(n):                       # all primes <= n
    if n < 2:
        return []
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for p in range(2, int(n ** 0.5) + 1):
        if is_prime[p]:
            for multiple in range(p * p, n + 1, p):
                is_prime[multiple] = False
    return [i for i, ok in enumerate(is_prime) if ok]


def mod_pow(base, exp, mod=MOD):    # O(log exp)
    result, base = 1, base % mod
    while exp > 0:
        if exp & 1:
            result = result * base % mod
        base = base * base % mod
        exp >>= 1
    return result

Common mistakes

  • Computing a × b before reducing when both are near 10⁹ overflows a 32-bit int — cast to 64-bit first.
  • In Python, negative numbers with % return a non-negative result; in C++/Java they can be negative. Add mod before taking % again.
  • Floating-point sqrt can be off by one for large n; prefer p * p <= n loops.

Quick check

Three questions on Math. Get all three right to earn +15 XP.

  1. What does gcd(48, 18) equal?

  2. To test whether n is prime by trial division, up to which number must you try divisors?

  3. Why do solutions compute (a * b) % MOD with 64-bit integers?

Challenges

Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.

Stuck on Math?Ask Orbi for a hint, a fresh explanation or a review of your code.

Ask the tutor