Modular Arithmetic Basics in DSA C

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. Numbers in modular arithmetic behave like hours on a clock, wrapping around after reaching the modulus.

Number line: 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 two numbers 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

Step 3: Result is the remainder 1

16 mod 5 = 1

Why: This is the final answer in modular arithmetic

Result:

1

Annotated Code

DSA C

#include <stdio.h>

// Function to compute (a + b) mod m
int modular_add(int a, int b, int m) {
    int sum = a + b; // add the numbers
    int result = sum % m; // find remainder after division by m
    if (result < 0) {
        result += m; // handle negative results to keep in range 0 to m-1
    }
    return result;
}

int main() {
    int a = 7, b = 9, m = 5;
    int res = modular_add(a, b, m);
    printf("(%d + %d) mod %d = %d\n", a, b, m, res);
    return 0;
}

int sum = a + b; // add the numbers

Add the two input numbers

int result = sum % m; // find remainder after division by m

Calculate remainder after dividing sum by modulus

if (result < 0) { result += m; } // handle negative results

Adjust negative remainder to positive equivalent

Output

(7 + 9) mod 5 = 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 approach might repeatedly subtract modulus until remainder found, which is slower; using % operator is efficient and direct

Edge Cases

Negative numbers as input

Result is adjusted to be within 0 to m-1 range

DSA C

if (result < 0) { result += m; }

Zero modulus (m = 0)

Undefined behavior, division by zero error

DSA C

No explicit guard; user must ensure m > 0

When to Use This Pattern

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

Common Mistakes

Mistake: Not handling negative results after modulus operation
Fix: Add modulus to negative remainder to keep result positive

Mistake: Using modulus zero which causes errors
Fix: Always ensure modulus is greater than zero before operation

Summary

It calculates the remainder after division by a fixed number called modulus.

Use it when numbers wrap around after reaching a limit, like clock hours or cyclic counters.

Remember modular arithmetic wraps numbers back to zero after reaching the modulus, like a clock resets after 12.

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