What Is Modular Arithmetic? The Coding Interview Explanation

The "count the ways" dynamic programming problem looks totally routine. Then the expected output says "return the answer modulo 10^9 + 7." And the room goes quiet. What does that mean? Why that specific number? Is this math? Did they change the problem halfway through? Why is there a prime involved?

Modular arithmetic is the math of remainders. It shows up constantly in coding interviews, but most prep resources bury it in a footnote. Once you actually understand what it is and why it exists, an entire category of problem constraints stops being confusing.

What Modular Arithmetic Actually Is

You already use it every day, without calling it that.

On a 12-hour clock, 10 hours after 5 o'clock is 3 o'clock, not 15. Fifteen wraps around. The clock resets every 12 hours. That's it. That's the whole idea.

15 mod 12 = 3

The general rule: a mod m is the non-negative remainder when you divide a by m. Formally, a = q × m + r where 0 ≤ r < m.

In code:

15 % 12  # 3
7 % 3    # 1
100 % 7  # 2

Once you take a mod, the result lives in [0, m-1], no matter how large the original number was. That's the whole point. You're capping the value. Turns out, interviewers have known this for years.

The correct answer is always zero. Modular arithmetic has been hiring people for decades.

Apply It at Every Step, Not Just at the End

You can apply the mod at each step of a computation without affecting the final result:

(a + b) % m  =  ((a % m) + (b % m)) % m
(a × b) % m  =  ((a % m) × (b % m)) % m

These hold for any integers a, b, and positive integer m. The power rule follows from repeated multiplication.

Consider counting paths in a grid. The true count might have thousands of digits. You can't store it. But if the problem says "return the answer mod 10^9 + 7," you reduce at every addition:

def count_paths(m: int, n: int) -> int:
    MOD = 10**9 + 7
    dp = [[1] * n for _ in range(m)]

    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD

    return dp[m-1][n-1]

Apply % MOD at each addition, not just at the end. If you wait, intermediate values overflow long before you get there. This is the single most common mistake, and it produces numbers so wrong that no debugger will help you.

Why 10^9 + 7?

This constant is everywhere. It's not arbitrary. It just looks arbitrary, which is arguably worse.

It's prime. Prime moduli unlock modular inverses and certain combinatorial proofs. You don't need the full theory for most interview problems, but it's why problem setters default to primes and specifically to this one.

It fits safely in 64-bit arithmetic. The maximum product before reducing is (10^9 + 6)^2 ≈ 10^18, which fits in a 64-bit integer (int64 max is about 9.2 × 10^18). So when you multiply two values already reduced mod 10^9 + 7, the product before reduction never overflows a long in Java or long long in C++.

It's large enough to be meaningful. A small modulus like 100 loses most of the information in the original number. 10^9 + 7 is large enough to be a useful fingerprint of the true answer, and small enough to be practical.

long M = 1_000_000_007L;
long a = 999_999_999L;
long b = 999_999_999L;

long result = (a * b) % M;  // safe: a * b fits in long

const long long M = 1e9 + 7;
long long a = 999999999LL;
long long b = 999999999LL;
long long result = (a * b) % M;  // fits in long long before mod

In Python this is never an issue because integers are arbitrary precision. In Java and C++, use long / long long explicitly before multiplying, or you'll silently overflow.

The Negative Modulo Trap

This one trips up engineers switching languages mid-prep. You've been writing Python for three months, you switch to Java for an interview, and suddenly your mod behavior changes on you.

-7 % 3   # 2 in Python (non-negative, sign follows divisor)

-7 % 3   // -1 in Java (sign follows dividend)

-7 % 3   // -1 in C++ (sign follows dividend since C++11)

-7 % 3   // -1 in Go (sign follows dividend)

Python gives a non-negative result. Java, C++, and Go give a result with the same sign as the left operand. If your solution subtracts before taking mod, you can silently produce a negative value in most languages.

The fix that works everywhere:

result = ((a - b) % m + m) % m

Adding m before the outer mod guarantees a non-negative result even when a < b. Make this a reflex whenever you subtract and then take a modulo. Write it without thinking. Do it before you think you need to.

The Overflow-Before-Mod Bug

Even when you remember to reduce frequently, there's a second trap. This one will hurt you specifically because the code looks completely correct when you read it.

int a = 1_000_000_006;
int b = 1_000_000_006;
int M = 1_000_000_007;

// Wrong: a * b overflows int before mod is applied
int result = (a * b) % M;

// Right: cast to long before multiplying
long result = (long) a * b % M;

The mod operation happens after the multiplication. If the multiplication overflows first, the result is garbage. You get a wrong answer with no error, no warning, and nothing visually off about the code.

Your code compiles. Your tests pass. The answer is wrong. The overflow happened before the mod.

In Java, cast at least one operand to long before the multiply. In Python, no issue. In C++, declare everything as long long.

This is the most common modular arithmetic bug in coding interviews. The logic is fine. The math is right. But the intermediate value silently wraps inside the int, and you spend 10 minutes staring at a numerically reasonable-looking incorrect answer.

Where You'll See It in Coding Interviews

"Return the answer modulo 10^9 + 7" is the direct signal. Any problem counting combinations, paths, or arrangements. Apply mod at every step.

Circular array indexing. Modular arithmetic replaces the conditional branch:

# Instead of: if i == size - 1: i = 0 else: i += 1
next_index = (i + 1) % size

# Stepping forward k positions in a circular buffer
target = (current + k) % size

Less branching, no edge cases.

Hash functions. Every hash table maps keys to bucket indices using modular arithmetic:

bucket = hash(key) % table_size

The rolling hash in Rabin-Karp works the same way: reduce the hash at each character so it stays bounded as the window slides across the string. The Rabin-Karp algorithm is the textbook example of modular arithmetic applied to string search.

Number manipulation. Extracting and dropping digits is just modular arithmetic on base 10:

last_digit = n % 10    # extract the ones place
n = n // 10            # drop the ones place

Cycle detection. By the pigeonhole principle, any sequence of integers mod m must repeat within m steps. This underpins Floyd's cycle detection algorithm and helps reason about the periodicity of sequences in certain problems.

Modular Exponentiation

When a problem asks you to compute a large power modulo something, naive exponentiation is too slow. Computing 2^1000000 step by step takes a million multiplications.

Binary exponentiation cuts this to O(log n) by squaring repeatedly:

def mod_pow(base: int, exp: int, mod: int) -> int:
    result = 1
    base = base % mod
    while exp > 0:
        if exp % 2 == 1:
            result = (result * base) % mod
        exp //= 2
        base = (base * base) % mod
    return result

In Python, the built-in pow(base, exp, mod) does exactly this and is implemented in C:

pow(2, 1_000_000, 10**9 + 7)  # O(log n), no intermediate overflow

Never write (base ** exp) % mod for large exponents. That computes base ** exp first, producing a number with millions of digits, and then takes the mod. The 3-argument pow form avoids this entirely. Python lets you be sloppy about a lot of things, but not this.

You'll see modular exponentiation in combinatorics problems requiring large factorials or binomial coefficients, and in matrix exponentiation problems like Fibonacci in O(log n). The binary exponentiation algorithm goes deeper if you want the full derivation.

Complexity

Both time and space are O(1) per operation. Modular arithmetic doesn't change the asymptotic complexity of your algorithm. One practical note: when the modulus is a power of two, you can use bitwise AND instead of division (n % 8 equals n & 7). For 10^9 + 7, there's no such shortcut. You just do the division.

If you want to practice explaining the 10^9 + 7 constraint out loud before the real interview catches you mid-sentence, SpaceComplexity runs voice-based mock interviews with rubric-based feedback. Knowing the material and being able to say it clearly under pressure are different skills. It's worth training both.

Further Reading

• Modular Arithmetic (Wikipedia)
• Modular Exponentiation (Wikipedia)
• Pigeonhole Principle (Wikipedia)
• Binary Exponentiation (cp-algorithms.com)
• Modular Arithmetic Problems (GeeksforGeeks)