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.

Practice

1. What is the result of 17 % 5 in modular arithmetic?

easy

A. 3

B. 2

C. 5

D. 12

Solution

1. Step 1: Understand the modulo operation

   The modulo operator (%) gives the remainder when the first number is divided by the second.

2. Step 2: Calculate 17 divided by 5

   17 divided by 5 is 3 with a remainder of 2.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   17 % 5 = 2 [OK]

Hint: Modulo gives remainder after division [OK]

Common Mistakes:

• Confusing modulo with division
• Using subtraction instead of modulo
• Mixing up dividend and divisor

2. Which of the following is the correct syntax to compute the remainder of 25 divided by 4 in Python?

easy

A. remainder = 25 % 4

B. remainder = 25 mod 4

C. remainder = 25 // 4

D. remainder = 25 / 4

Solution

1. Step 1: Recall Python modulo operator

   In Python, the modulo operator is the percent sign (%).

2. Step 2: Check each option

   remainder = 25 % 4 uses 25 % 4 which correctly computes the remainder. remainder = 25 mod 4 uses 'mod' which is not valid syntax. remainder = 25 // 4 uses floor division (//) which gives quotient, not remainder. remainder = 25 / 4 uses normal division (/), which gives a float result.

3. Final Answer:

   remainder = 25 % 4 -> Option A

4. Quick Check:

   Use % for modulo in Python [OK]

Hint: Use % symbol for modulo in Python [OK]

Common Mistakes:

• Using 'mod' keyword
• Confusing // with %
• Using / instead of %

3. What is the output of the following Python code?

for i in range(1, 6):
    print(i % 3, end=' ')

medium

A. 0 1 2 0 1

B. 1 2 3 1 2

C. 1 2 0 1 2

D. 1 2 0 2 1

Solution

1. Step 1: Understand the loop and modulo

   The loop runs i from 1 to 5. For each i, we compute i % 3.

2. Step 2: Calculate each modulo

   1 % 3 = 1, 2 % 3 = 2, 3 % 3 = 0, 4 % 3 = 1, 5 % 3 = 2.

3. Final Answer:

   1 2 0 1 2 -> Option C

4. Quick Check:

   Modulo cycles every 3 numbers [OK]

Hint: Modulo repeats remainder pattern every divisor [OK]

Common Mistakes:

• Starting loop at 0 instead of 1
• Miscomputing modulo for 3
• Confusing modulo with division

4. Find the error in the following code snippet that tries to compute n % 4 for n = 10:

n = 10
result = n %
print(result)

medium

A. Missing operand after % operator

B. Incorrect variable name

C. Using print without parentheses

D. No error, code runs fine

Solution

1. Step 1: Analyze the modulo expression

   The line 'result = n %' is incomplete because modulo requires two operands: dividend and divisor.

2. Step 2: Identify syntax error

   Without a number or variable after %, Python will raise a syntax error.

3. Final Answer:

   Missing operand after % operator -> Option A

4. Quick Check:

   Modulo needs two numbers: a % b [OK]

Hint: Modulo operator needs both numbers [OK]

Common Mistakes:

• Leaving out divisor after %
• Using print without () in Python 3
• Typos in variable names

5. You want to find the remainder when the sum of numbers from 1 to 100 is divided by 7. Which Python expression correctly computes this using modular arithmetic?

hard

A. sum(i for i in range(1, 101)) // 7

B. (sum(range(1, 101)) // 7) % 7

C. sum(i % 7 for i in range(1, 101))

D. sum(range(1, 101)) % 7

Solution

1. Step 1: Understand the problem

   We want the remainder of the sum of numbers 1 to 100 divided by 7.

2. Step 2: Evaluate each option

   sum(range(1, 101)) % 7 correctly sums all numbers then applies modulo 7. (sum(range(1, 101)) // 7) % 7 first does floor division to get quotient then % 7, which is incorrect. sum(i % 7 for i in range(1, 101)) sums remainders but does not apply modulo to the total sum, so it gives a wrong result. sum(i for i in range(1, 101)) // 7 uses floor division (//) which gives quotient, not remainder.

3. Final Answer:

   sum(range(1, 101)) % 7 -> Option D

4. Quick Check:

   Sum then modulo gives remainder [OK]

Hint: Sum first, then modulo for remainder [OK]

Common Mistakes:

• Applying modulo inside sum without final modulo
• Using floor division instead of modulo
• Using floor division before modulo