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.