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 reset like the clock 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 sum of 7 and 9, then wrap it around modulus 5 to get the remainder

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 remainder after division by 5

Step 3: Result is the remainder 1

Final result = 1

Why: The sum wraps around modulus 5 to 1

Result:

1

Annotated Code

DSA C++

#include <iostream>
using namespace std;

// Function to perform modular addition
int mod_add(int a, int b, int mod) {
    int sum = a + b; // add the two numbers
    int result = sum % mod; // find remainder after division by mod
    return result; // return the wrapped around value
}

int main() {
    int a = 7, b = 9, mod = 5;
    int answer = mod_add(a, b, mod);
    cout << answer << "\n"; // print the result
    return 0;
}

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

Add the input numbers normally

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

Apply modulus to wrap the sum around

return result; // return the wrapped around value

Return the final modular result

Output

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 addition without modulus can cause overflow or incorrect results in modular problems; modular arithmetic keeps numbers within bounds efficiently

Edge Cases

Sum is exactly divisible by modulus

Result is zero because remainder is zero

DSA C++

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

One or both numbers are zero

Result is simply the other number modulo mod

DSA C++

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

Numbers larger than modulus

Sum can be larger than modulus but result wraps correctly due to modulus operation

DSA C++

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

When to Use This Pattern

When you see problems involving large numbers or wrap-around behavior, reach for modular arithmetic because it keeps numbers within a fixed range safely.

Common Mistakes

Mistake: Forgetting to apply modulus after addition, causing wrong results
Fix: Always apply modulus operator (%) after arithmetic operations to wrap values

Summary

It calculates the remainder after dividing the sum of two numbers by a modulus.

Use it when you want numbers to wrap around after reaching a certain limit.

The key insight is that modular arithmetic works like a clock that resets after a fixed number.

Practice

1. What is the result of 17 % 5 in modular arithmetic?

easy

A. 5

B. 3

C. 2

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 17 % 5

   Dividing 17 by 5 gives 3 with a remainder of 2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   17 divided by 5 leaves remainder 2 [OK]

Hint: Modulo gives remainder after division [OK]

Common Mistakes:

• Confusing modulo with division
• Using 5 instead of remainder
• Ignoring remainder sign

2. Which of the following is the correct syntax to compute the modulo of two integers a and b in C++?

easy

A. a // b

B. a mod b

C. mod(a, b)

D. a % b

Solution

1. Step 1: Recall C++ modulo operator syntax

   In C++, the modulo operator is represented by the percent sign (%).

2. Step 2: Identify correct syntax

   Among the options, only a % b is valid C++ syntax for modulo.

3. Final Answer:

   a % b -> Option D

4. Quick Check:

   C++ uses % for modulo [OK]

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

Common Mistakes:

• Using 'mod' keyword
• Using '//' which is floor division in some languages
• Using function call syntax incorrectly

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

int a = 14;
int b = 4;
int c = (a + b) % 5;
std::cout << c << std::endl;

medium

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Calculate sum inside parentheses

   a + b = 14 + 4 = 18.

2. Step 2: Calculate modulo 5 of the sum

   18 % 5 = 3 because 5 * 3 = 15 and remainder is 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

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

Hint: Add first, then modulo [OK]

Common Mistakes:

• Modulo before addition
• Wrong remainder calculation
• Confusing output with sum

4. Identify the error in the following C++ code snippet that tries to compute modulo:

int x = 10;
int y = 0;
int z = x % y;
std::cout << z << std::endl;

medium

A. Syntax error in modulo operator

B. Division by zero error

C. Variable z not declared

D. No error, code runs fine

Solution

1. Step 1: Check modulo divisor value

   The divisor y is 0, which is invalid for modulo operation.

2. Step 2: Understand runtime behavior

   Modulo by zero causes a runtime error (division by zero).

3. Final Answer:

   Division by zero error -> Option B

4. Quick Check:

   Modulo divisor cannot be zero [OK]

Hint: Modulo divisor must not be zero [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 can be very large?

hard

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

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

C. Use ((long long)a * b) % m

D. Use (a * b) % m directly

Solution

1. Step 1: Understand integer overflow risk

   Multiplying large int values a and b directly can cause undefined behavior due to overflow before % m.

2. Step 2: Safe computation using modulo properties

   Using ((a % m) * (b % m)) % m ensures intermediate values stay within range and prevents overflow.

3. Step 3: Why others fail

   ((long long)a * b) % m may still overflow if b is large and not casted. (a % m) * (b % m) misses final modulo. (a * b) % m overflows.

4. Final Answer:

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

5. Quick Check:

   Modulo before multiply and after prevents overflow [OK]

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

Common Mistakes:

• Modulo before multiply without final modulo
• Missing final modulo
• Direct multiplication without modulo