Modular Arithmetic Basics in DSA C++ - Execution Trace

Concept Flow - Modular Arithmetic Basics

Start with two numbers a and b

↓

Choose modulus m

↓

Calculate a mod m

↓

Calculate b mod m

↓

Perform operation (add, sub, mul) on results

↓

Take result mod m

↓

Result

Shows how to compute modular arithmetic by reducing numbers modulo m before and after operations.

Execution Sample

DSA C++

int a = 17;
int b = 23;
int m = 10;
int result = (a + b) % m;
std::cout << result << std::endl;

Adds 17 and 23, then finds remainder when divided by 10.

Execution Table

Step	Operation	Value(s) Involved	Intermediate Result	Final Result (mod 10)
1	Calculate a mod m	a=17, m=10	17 % 10 = 7	7
2	Calculate b mod m	b=23, m=10	23 % 10 = 3	3
3	Add reduced values	7 + 3	10	10
4	Take sum mod m	10 % 10	0	0
5	Output result	result = 0	-	0

💡 Completed modular addition and output result.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
a	17	17	17	17	17	17
b	23	23	23	23	23	23
m	10	10	10	10	10	10
a mod m	-	7	7	7	7	7
b mod m	-	-	3	3	3	3
sum	-	-	-	10	10	10
result	-	-	-	-	0	0

Key Moments - 3 Insights

Why do we take modulo of each number before adding?

Taking modulo before addition keeps numbers small and avoids overflow, as shown in steps 1 and 2 where a and b are reduced before adding in step 3.

Why do we take modulo again after addition?

Because sum can be equal or larger than modulus, taking modulo again (step 4) ensures the final result stays within 0 to m-1.

What happens if we skip modulo after addition?

The result might be larger than modulus and not represent the correct modular sum, breaking modular arithmetic rules.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of 'b mod m' after step 2?

A 3

B 7

C 0

D 23

💡 Hint

Check the 'Intermediate Result' column at step 2 in the execution table.

At which step does the sum exceed the modulus before taking modulo again?

A Step 4

B Step 1

C Step 3

D Step 5

💡 Hint

Look at the 'Intermediate Result' column for the sum in the execution table.

If modulus m was changed to 15, what would be the final result after addition and modulo?

A 0

B 10

C 5

D 7

💡 Hint

Calculate (17 + 23) % 15 and compare with the execution table logic.

Concept Snapshot

Modular Arithmetic Basics:
- Use '%' operator to find remainder.
- Reduce operands modulo m before operations.
- Perform operation (add, sub, mul) on reduced values.
- Take modulo m of the result to keep within range.
- Useful to avoid overflow and keep numbers small.

Full Transcript

This lesson shows how to perform modular arithmetic by reducing numbers modulo a chosen modulus before and after arithmetic operations. We start with two numbers, a and b, and a modulus m. We find a mod m and b mod m to keep numbers small. Then we add these reduced values and take modulo m again to get the final result. This ensures the result stays within 0 to m-1. The example adds 17 and 23 with modulus 10, resulting in 0. Key points include why modulo is taken before and after addition to avoid overflow and maintain correctness.

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