Modular Arithmetic Basics in DSA Typescript - Execution Trace

Concept Flow - Modular Arithmetic Basics

Start with numbers a and b

↓

Choose modulus m

↓

Calculate a mod m

↓

Calculate b mod m

↓

Perform operation (add, subtract, multiply) on results

↓

Take result mod m

↓

Result

Start with two numbers and a modulus. Find their remainders mod m, perform the operation, then take mod m again to get the final result.

Execution Sample

DSA Typescript

const a = 17;
const b = 23;
const m = 5;
const result = ((a % m) + (b % m)) % m;
console.log(result);

Adds 17 and 23 under modulus 5 and prints the remainder.

Execution Table

Step	Operation	Value(s)	Intermediate Result	Visual State
1	Calculate a mod m	17 % 5	2	a mod m = 2
2	Calculate b mod m	23 % 5	3	b mod m = 3
3	Add results	2 + 3	5	Sum before mod = 5
4	Take mod m of sum	5 % 5	0	Final result = 0
5	Print result	result = 0	0	Output: 0
6	End	-	-	Computation complete

💡 All steps done; final modular addition result is 0.

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	5	5	5	5	5	5
a_mod	-	2	2	2	2	2
b_mod	-	-	3	3	3	3
sum	-	-	-	5	5	5
result	-	-	-	-	0	0

Key Moments - 3 Insights

Why do we take mod of each number before adding?

Taking mod of each number first keeps numbers small and avoids overflow, as shown in steps 1 and 2 of the execution_table.

Why do we take mod again after adding?

Adding two mod results can exceed the modulus, so we take mod again (step 4) to keep the final result within range.

What if the sum before mod equals the modulus?

If sum equals modulus (step 3 shows sum=5 and m=5), mod returns 0, which is the correct remainder.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of a_mod after step 1?

A 2

B 3

C 0

D 5

💡 Hint

Check the 'Intermediate Result' column at step 1.

At which step does the sum before taking mod equal the modulus?

A Step 4

B Step 2

C Step 3

D Step 5

💡 Hint

Look at the 'Value(s)' and 'Intermediate Result' columns for sum and modulus.

If we changed m from 5 to 6, what would be the final result after step 4?

A 0

B 4

C 1

D 5

💡 Hint

Calculate (17 % 6) + (23 % 6) then mod 6, referencing variable_tracker values.

Concept Snapshot

Modular Arithmetic Basics:
- Use '%' operator to find remainder.
- Compute each number mod m first.
- Perform operation (add, subtract, multiply).
- Take mod m of the result to keep within range.
- Useful for wrapping numbers in cycles.

Full Transcript

Modular arithmetic means working with remainders after division by a number called modulus. We start with two numbers, a and b, and a modulus m. We find the remainder of a divided by m, then the remainder of b divided by m. Next, we add these remainders. Because the sum might be bigger than m, we take the remainder of the sum divided by m again. This final remainder is the modular sum. This process keeps numbers small and cycles them within 0 to m-1. For example, with a=17, b=23, and m=5, a mod m is 2, b mod m is 3, sum is 5, and 5 mod 5 is 0. So the modular sum is 0.

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 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*2 + 1, the remainder 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 remainder with quotient
• Thinking modulo returns division result
• Mixing up dividend and divisor

2. Which of the following is the correct TypeScript syntax to compute the remainder of a divided by b?

easy

A. let result = a % b;

B. let result = a / b;

C. let result = a mod b;

D. let result = a & b;

Solution

1. Step 1: Recall TypeScript modulo operator

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

2. Step 2: Identify correct syntax

   let result = a % b; uses a % b, which correctly computes the remainder.

3. Final Answer:

   let result = a % b; -> Option A

4. Quick Check:

   Modulo operator is % in TypeScript [OK]

Hint: Use % for modulo in TypeScript [OK]

Common Mistakes:

• Using / instead of %
• Using 'mod' keyword which doesn't exist
• Using bitwise & operator by mistake

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

const a = 14;
const b = 5;
console.log(a % b);

medium

A. 3

B. 4

C. 2

D. 0

Solution

1. Step 1: Calculate 14 % 5

   Divide 14 by 5: 5 * 2 = 10, remainder is 14 - 10 = 4.

2. Step 2: Confirm output

   The console.log prints the remainder, which is 4.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   14 % 5 = 4 [OK]

Hint: Modulo is remainder after division [OK]

Common Mistakes:

• Calculating quotient instead of remainder
• Mixing up operands order
• Assuming modulo returns division result

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

function mod(a: number, b: number): number {
  return a % b;
}

console.log(mod(10, 0));

medium

A. Syntax error due to missing semicolon

B. No error, outputs 0

C. Runtime error: division by zero

D. Returns NaN without error

Solution

1. Step 1: Analyze modulo with zero divisor

   In TypeScript/JavaScript, modulo by zero returns NaN and does NOT throw a runtime error.

2. Step 2: Understand error behavior

   Calling mod(10, 0) computes 10 % 0 which is NaN, and console.log prints NaN.

3. Final Answer:

   Returns NaN without error -> Option D

4. Quick Check:

   10 % 0 = NaN [OK]

Hint: Modulo by zero returns NaN in TypeScript [OK]

Common Mistakes:

• Thinking modulo by zero causes runtime error
• Assuming modulo by zero returns 0
• Confusing with languages that raise exceptions

5. You want to find the remainder when the sum of two large numbers a = 123456789 and b = 987654321 is divided by m = 1000. Which expression correctly uses modular arithmetic to compute (a + b) % m without overflow?

hard

A. (a + b) % m

B. a % (b % m)

C. (a % m + b % m) % m

D. (a % b) + (b % m)

Solution

1. Step 1: Understand modular addition property

   Modular arithmetic allows splitting sums: (a + b) % m = ((a % m) + (b % m)) % m.

2. Step 2: Apply property to avoid overflow

   Computing (a % m + b % m) % m prevents large intermediate sums and overflow.

3. Step 3: Check other options

   (a + b) % m risks overflow; B and D misuse modulo operations.

4. Final Answer:

   (a % m + b % m) % m -> Option C

5. Quick Check:

   Use modular addition property [OK]

Hint: Add remainders then modulo again to avoid overflow [OK]

Common Mistakes:

• Directly adding large numbers before modulo
• Misusing modulo on operands incorrectly
• Ignoring overflow in large sums