Modular Arithmetic Basics in DSA Python

Mental Model

Modular arithmetic means working with numbers that wrap around after reaching a certain value, called the modulus.

Analogy: Think of a clock: after 12 hours, it goes back to 1. The clock numbers wrap around just like modular arithmetic wraps numbers after the modulus.

Numbers: 0 -> 1 -> 2 -> ... -> (modulus - 1) -> back to 0
Example with modulus 5:
0 -> 1 -> 2 -> 3 -> 4 -> back to 0

Dry Run Walkthrough

Input: Calculate (7 + 9) mod 5

Goal: Find the remainder when the sum of 7 and 9 is divided by 5

Step 1: Add 7 and 9 to get 16

Sum = 16

Why: We first add the numbers normally before applying the modulus

Step 2: Divide 16 by 5 and find the remainder

16 ÷ 5 = 3 remainder 1

Why: Modulus means remainder after division by 5

Step 3: Result is the remainder 1

16 mod 5 = 1

Why: The final modular sum wraps around to 1

Result:

1

Annotated Code

DSA Python

class ModularArithmetic:
    def __init__(self, modulus: int):
        self.modulus = modulus

    def add(self, a: int, b: int) -> int:
        # Add two numbers and take modulus
        total = a + b
        result = total % self.modulus
        return result

# Driver code
mod = ModularArithmetic(5)
result = mod.add(7, 9)
print(result)

total = a + b

Add the two input numbers

result = total % self.modulus

Apply modulus to wrap the sum within range

return result

Return the modular sum

Output

1

Complexity Analysis

Time: O(1) because addition and modulus operations take constant time

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Naive addition without modulus can cause numbers to grow large and overflow; modular arithmetic keeps numbers small and manageable

Edge Cases

Adding zero

Result is the other number modulo the modulus

DSA Python

result = total % self.modulus

Adding numbers equal to or larger than modulus

Sum wraps correctly within modulus range

DSA Python

result = total % self.modulus

Modulus is 1

All results are zero because any number mod 1 is zero

DSA Python

result = total % self.modulus

When to Use This Pattern

When you see problems asking for results 'mod' some number, use modular arithmetic to keep numbers small and avoid overflow.

Common Mistakes

Mistake: Forgetting to apply modulus after addition
Fix: Always apply modulus operator (%) after arithmetic operations to wrap the result

Summary

Modular arithmetic calculates remainders after division by a fixed number called modulus.

Use it when you want numbers to wrap around after reaching a limit, like clock hours or large number computations.

The key insight is that numbers reset to zero after reaching the modulus, keeping values within a fixed range.