Modular Arithmetic Basics in DSA Typescript

Mental Model

Modular arithmetic means counting numbers but wrapping around after reaching a certain value, like a clock resets after 12.

Analogy: Think of a clock showing hours from 1 to 12. After 12, it goes back to 1. This wrapping around is modular arithmetic.

Numbers: 0 1 2 3 4 5 6 7 8 9
Modulus: 10
Example: 7 + 5 = 12 -> wraps to 2 (because 12 mod 10 = 2)

Dry Run Walkthrough

Input: Calculate (7 + 5) mod 10 and (9 * 4) mod 10

Goal: Show how addition and multiplication wrap around using modulus 10

Step 1: Add 7 and 5 to get 12

7 + 5 = 12

Why: We first do normal addition before applying the wrap-around

Step 2: Apply modulus 10 to 12 to get remainder 2

12 mod 10 = 2

Why: We wrap around by taking the remainder after division by 10

Step 3: Multiply 9 and 4 to get 36

9 * 4 = 36

Why: We do normal multiplication before wrapping

Step 4: Apply modulus 10 to 36 to get remainder 6

36 mod 10 = 6

Why: Wrap around by taking the remainder after division by 10

Result:

7 + 5 mod 10 = 2
9 * 4 mod 10 = 6

Annotated Code

DSA Typescript

class ModularArithmetic {
  modulus: number;

  constructor(modulus: number) {
    this.modulus = modulus;
  }

  add(a: number, b: number): number {
    const sum = a + b;
    return sum % this.modulus; // wrap around after modulus
  }

  multiply(a: number, b: number): number {
    const product = a * b;
    return product % this.modulus; // wrap around after modulus
  }
}

// Driver code
const modArith = new ModularArithmetic(10);
const addResult = modArith.add(7, 5);
const mulResult = modArith.multiply(9, 4);
console.log(`${7} + ${5} mod 10 = ${addResult}`);
console.log(`${9} * ${4} mod 10 = ${mulResult}`);

return sum % this.modulus; // wrap around after modulus

apply modulus operator to wrap sum within range

return product % this.modulus; // wrap around after modulus

apply modulus operator to wrap product within range

Output

7 + 5 mod 10 = 2

9 * 4 mod 10 = 6

Complexity Analysis

Time: O(1) because addition, multiplication, and modulus operations take constant time

Space: O(1) because no extra space is used beyond variables

vs Alternative: Modular arithmetic is much faster and simpler than repeatedly subtracting the modulus manually

Edge Cases

Adding numbers smaller than modulus

Result is normal sum without wrapping

DSA Typescript

return sum % this.modulus; // wrap around after modulus

Multiplying by zero

Result is zero, no wrapping needed

DSA Typescript

return product % this.modulus; // wrap around after modulus

Numbers equal to modulus

Result wraps to zero

DSA Typescript

return sum % this.modulus; // wrap around after modulus

When to Use This Pattern

When you see problems involving repeating cycles or wrap-around counting, use modular arithmetic to simplify calculations.

Common Mistakes

Mistake: Forgetting to apply modulus after addition or multiplication
Fix: Always apply the modulus operator (%) after arithmetic to keep results within range

Summary

Modular arithmetic wraps numbers around after reaching a fixed modulus.

Use it when counting cycles or when numbers should stay within a fixed range.

The key insight is that results always stay between 0 and modulus-1 by using the remainder operation.

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