Why Modular Arithmetic Basics in DSA Python?

The Big Idea

What if you could make confusing number cycles simple and error-free with just one rule?

The Scenario

Imagine you are trying to keep track of hours on a clock. When the hour hand passes 12, it starts again at 1. Doing this by just adding numbers without any rule can get confusing quickly.

The Problem

Without a clear rule, adding hours manually can lead to mistakes like saying 13 o'clock or 25 o'clock, which don't exist on a clock. This makes calculations slow and error-prone.

The Solution

Modular arithmetic gives a simple rule: after reaching a certain number (like 12 on a clock), start back at zero. This keeps numbers within a fixed range and makes calculations neat and reliable.

Before vs After

✗ Before

hour = 10
hour = hour + 5
if hour > 12:
    hour = hour - 12

✓ After

hour = 10
hour = (hour + 5) % 12
if hour == 0:
    hour = 12

What It Enables

It allows us to work with repeating cycles easily, like clocks, calendars, or wrapping around arrays.

Real Life Example

Calculating the day of the week after a certain number of days, where after Sunday comes Monday again, uses modular arithmetic.

Key Takeaways

Modular arithmetic keeps numbers within a fixed range by wrapping around.

It simplifies calculations involving cycles or repeats.

It prevents errors from numbers growing too large or going out of expected bounds.

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