Modular Arithmetic Basics in DSA C - Time & Space Complexity

Time Complexity: Modular Arithmetic Basics

O(1)

Understanding Time Complexity

We want to understand how long modular arithmetic operations take as numbers get bigger.

How does the time to compute remainders grow with input size?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int mod_add(int a, int b, int m) {
    return (a % m + b % m) % m;
}

int mod_mul(int a, int b, int m) {
    return (int)(((long long)(a % m) * (b % m)) % m);
}
    

This code performs modular addition and modular multiplication of two integers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The modulo (%) operator applied to integers.
• How many times: Each modulo operation runs once per function call.

How Execution Grows With Input

The modulo operation takes roughly the same time regardless of the size of the numbers because it is a single division step.

Input Size (n)	Approx. Operations
10	3 modulo operations
100	3 modulo operations
1000	3 modulo operations

Pattern observation: The number of operations stays the same no matter how big the input numbers are.

Final Time Complexity

Time Complexity: O(1)

This means the time to do modular addition or multiplication does not grow with input size; it stays constant.

Common Mistake

[X] Wrong: "Modular arithmetic takes longer as numbers get bigger because of the modulo operation."

[OK] Correct: The modulo operation is a single division step handled efficiently by the processor, so its time does not increase with number size in typical integer ranges.

Interview Connect

Understanding that modular arithmetic operations run in constant time helps you reason about algorithms that use them, like hashing or cryptography, which is a valuable skill in coding interviews.

Self-Check

"What if we used very large numbers beyond standard integer size, requiring multiple-precision arithmetic? How would the time complexity change?"

Practice

1. What is the result of 7 % 3 in modular arithmetic?

easy

A. 1

B. 2

C. 3

D. 0

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 7 % 3

   7 divided by 3 is 2 with a remainder of 1, but since 7 % 3 means remainder, it is 1.

3. Final Answer:

   1 -> Option A

4. Quick Check:

   7 % 3 = 1 [OK]

Hint: Modulo gives remainder after division [OK]

Common Mistakes:

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

2. Which of the following is the correct syntax to compute the remainder of a divided by b in C?

easy

A. a mod b

B. a % b

C. mod(a, b)

D. a / b

Solution

1. Step 1: Recall C syntax for modulo

   In C, the modulo operator is represented by the percent sign '%'.

2. Step 2: Identify correct syntax

   The correct way to get remainder is a % b. Other options are invalid syntax or division.

3. Final Answer:

   a % b -> Option B

4. Quick Check:

   Modulo operator in C is % [OK]

Hint: Use % operator for modulo in C [OK]

Common Mistakes:

• Using 'mod' keyword
• Using division operator '/' instead
• Calling a function mod() which doesn't exist in C

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

#include 
int main() {
    int x = 14;
    int y = 5;
    printf("%d", (x + y) % y);
    return 0;
}

medium

A. 4

B. 0

C. 1

D. 5

Solution

1. Step 1: Calculate (x + y)

   x = 14, y = 5, so x + y = 19.

2. Step 2: Calculate (x + y) % y

   19 % 5 is the remainder when 19 is divided by 5. 5 * 3 = 15, remainder 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   (14 + 5) % 5 = 4 [OK]

Hint: Add first, then apply modulo [OK]

Common Mistakes:

• Applying modulo before addition
• Confusing remainder with quotient
• Incorrect operator precedence

4. Identify the error in the following C code snippet that attempts to compute a % b:

int a = 10;
int b = 0;
int c = a % b;
printf("%d", c);

medium

A. Syntax error in modulo operator

B. Variable c is not declared

C. Division by zero error

D. No error, code runs fine

Solution

1. Step 1: Check divisor value

   Variable b is zero, which is the divisor in modulo operation.

2. Step 2: Understand modulo with zero divisor

   Modulo by zero is undefined and causes a runtime error (division by zero).

3. Final Answer:

   Division by zero error -> Option C

4. Quick Check:

   Modulo divisor cannot be zero [OK]

Hint: Never modulo by zero; it causes runtime error [OK]

Common Mistakes:

• Ignoring zero divisor
• Assuming modulo by zero returns zero
• Confusing syntax error with runtime error

5. Given the expression (a * b) % m, which of the following is a correct way to compute it without causing integer overflow in C when a and b are large integers?

hard

A. Use (a % b) % m

B. Use (a * b) % m directly

C. Use (a + b) % m

D. Use ((a % m) * (b % m)) % m

Solution

1. Step 1: Understand overflow risk

   Multiplying large integers a * b can overflow before modulo is applied.

2. Step 2: Apply modular multiplication property

   Using ((a % m) * (b % m)) % m keeps intermediate values smaller, preventing overflow.

3. Final Answer:

   ((a % m) * (b % m)) % m -> Option D

4. Quick Check:

   Modular multiplication reduces overflow risk [OK]

Hint: Modulo each operand before multiply to avoid overflow [OK]

Common Mistakes:

• Multiplying before modulo causing overflow
• Using addition instead of multiplication
• Incorrect modulo order