Modular Arithmetic Basics in DSA Python - Time & Space Complexity

Time Complexity: Modular Arithmetic Basics

O(1)

Understanding Time Complexity

We want to understand how the time to do modular arithmetic operations changes as numbers get bigger.

How does the number size affect the steps needed to find the remainder?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def mod_add(a, b, m):
    return (a + b) % m

result = mod_add(123456789, 987654321, 1000000007)
print(result)

This code adds two numbers and finds the remainder when divided by m.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Addition and modulo operation on integers.
• How many times: Only once per function call, no loops or recursion.

How Execution Grows With Input

As the numbers get bigger, the time to add and find remainder grows very slowly because these are simple operations.

Input Size (number of digits)	Approx. Operations
10 digits	Few basic steps
100 digits	More steps but still fast
1000 digits	More steps but grows slowly

Pattern observation: The time grows roughly proportional to the number of digits, not the number size itself.

Final Time Complexity

Time Complexity: O(1)

This means the operation takes constant time for normal fixed-size integers because addition and modulo are simple CPU instructions.

Common Mistake

[X] Wrong: "Modular arithmetic takes longer as numbers get bigger because the numbers are larger."

[OK] Correct: For fixed-size integers, addition and modulo are done in constant time by the processor, so size does not affect time.

Interview Connect

Understanding modular arithmetic time helps you explain why many algorithms use it for fast calculations with large numbers.

Self-Check

"What if we used very large numbers beyond normal integer size, like big integers? How would the time complexity change?"

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