Modular Arithmetic Basics in DSA Rust

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 the hours on a clock.

Numbers: 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 numbers normally before applying the modulus

Step 2: Divide 16 by 5 and find the remainder

16 ÷ 5 = 3 remainder 1

Why: Modulus means the remainder after division by 5

Step 3: Result is the remainder 1

Final result = 1

Why: The answer in modular arithmetic is always the remainder

Result:

Final result: 1

Annotated Code

DSA Rust

fn mod_add(a: i32, b: i32, modulus: i32) -> i32 {
    let sum = a + b; // add the two numbers
    let result = sum % modulus; // find remainder after division by modulus
    if result < 0 { // handle negative results
        result + modulus
    } else {
        result
    }
}

fn main() {
    let a = 7;
    let b = 9;
    let modulus = 5;
    let result = mod_add(a, b, modulus);
    println!("({} + {}) mod {} = {}", a, b, modulus, result);
}

let sum = a + b; // add the two numbers

add inputs before applying modulus

let result = sum % modulus; // find remainder after division by modulus

calculate remainder to wrap number within modulus range

if result < 0 { result + modulus } else { result }

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 repeated subtraction to find remainder is slower (O(n)), modulus operator is efficient and direct

Edge Cases

Negative sum (e.g., a = -3, b = 1, modulus = 5)

Result is adjusted to a positive remainder within 0 to modulus-1

DSA Rust

if result < 0 { result + modulus } else { result }

Sum exactly divisible by modulus (e.g., a = 5, b = 10, modulus = 5)

Result is zero as remainder is zero

DSA Rust

let result = sum % modulus;

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 from modulus operation
Fix: Add modulus to negative remainder to get correct positive result

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 large number computations.

Remember modular arithmetic is like a clock where numbers reset after reaching the modulus.

Practice

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

easy

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Understand the modulo operation

   The modulo operator (%) gives the remainder after division of the first number by the second.

2. Step 2: Calculate 7 modulo 3

   7 divided by 3 is 2 with a remainder of 1, so 7 % 3 = 1.

3. Final Answer:

   1 -> Option A

4. Quick Check:

   7 % 3 = 1 [OK]

Hint: Modulo gives remainder after division [OK]

Common Mistakes:

• Confusing modulo with division
• Using 3 instead of remainder
• Thinking modulo returns quotient

2. Which of the following is the correct Rust syntax to compute the remainder of 15 divided by 4?

easy

A. let result = 15 / 4;

B. let result = 15 mod 4;

C. let result = 15 % 4;

D. let result = 15 rem 4;

Solution

1. Step 1: Recall Rust modulo syntax

   In Rust, the modulo operator is the percent sign (%), not 'mod' or 'rem'.

2. Step 2: Identify correct syntax

   let result = 15 % 4; uses % correctly: let result = 15 % 4;

3. Final Answer:

   let result = 15 % 4; -> Option C

4. Quick Check:

   Rust uses % for modulo [OK]

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

Common Mistakes:

• Using 'mod' keyword incorrectly
• Using division operator instead of modulo
• Using 'rem' which is invalid syntax

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

fn main() {
    let a = 10;
    let b = 6;
    let c = (a + b) % 7;
    println!("{}", c);
}

medium

A. 4

B. 2

C. 3

D. 1

Solution

1. Step 1: Calculate sum inside parentheses

   a + b = 10 + 6 = 16.

2. Step 2: Compute modulo 7 of the sum

   16 % 7 = 2 (because 7 * 2 = 14, remainder 2).

3. Step 3: Check printed output

   The code prints the value of c, which is 2.

4. Final Answer:

   2 -> Option B

5. Quick Check:

   (10 + 6) % 7 = 2 [OK]

Hint: Calculate sum first, then modulo [OK]

Common Mistakes:

• Modulo before addition
• Wrong remainder calculation
• Confusing modulo with division

4. Identify the error in this Rust code snippet that tries to compute modulo:

fn main() {
    let x = 20;
    let y = 0;
    let z = x % y;
    println!("{}", z);
}

medium

A. Division by zero error at runtime

B. Syntax error: % operator not allowed

C. Variable y is not initialized

D. No error, code runs fine

Solution

1. Step 1: Analyze modulo operation with zero divisor

   Modulo by zero is undefined and causes a runtime error in Rust.

2. Step 2: Identify error type

   The code will compile but panic at runtime due to division by zero.

3. Final Answer:

   Division by zero error at runtime -> Option A

4. Quick Check:

   Modulo by zero causes runtime panic [OK]

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

Common Mistakes:

• Thinking it's a syntax error
• Ignoring zero divisor
• Assuming code runs fine

5. You want to compute (a * b) % m for very large integers a and b in Rust without overflow. Which approach is best?

hard

A. Compute a * b first, then modulo m

B. Convert numbers to strings and then modulo

C. Use floating point multiplication and then modulo

D. Use modular multiplication: ((a % m) * (b % m)) % m

Solution

1. Step 1: Understand overflow risk

   Multiplying large integers directly can overflow before modulo is applied.

2. Step 2: Apply modular multiplication property

   Using ((a % m) * (b % m)) % m keeps intermediate values small and avoids overflow.

3. Step 3: Evaluate other options

   Compute a * b first, then modulo m risks overflow; options B and C are invalid or inefficient.

4. Final Answer:

   Use modular multiplication: ((a % m) * (b % m)) % m -> Option D

5. Quick Check:

   (a * b) % m = ((a % m) * (b % m)) % m [OK]

Hint: Apply modulo before multiplication to avoid overflow [OK]

Common Mistakes:

• Multiplying before modulo causing overflow
• Using floats incorrectly
• String conversion misuse