Modular Arithmetic Basics in DSA Javascript

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. The clock numbers wrap around just like modular arithmetic wraps numbers after the modulus.

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 gives the remainder after division

Step 3: Result is the remainder 1

16 mod 5 = 1

Why: The final answer is the remainder after division

Result:

1

Annotated Code

DSA Javascript

class ModularArithmetic {
  constructor(modulus) {
    this.modulus = modulus;
  }

  add(a, b) {
    // Add numbers and apply modulus to wrap around
    return (a + b) % this.modulus;
  }
}

// Driver code
const mod = new ModularArithmetic(5);
const a = 7;
const b = 9;
const result = mod.add(a, b);
console.log(`${a} + ${b} mod ${mod.modulus} = ${result}`);

return (a + b) % this.modulus;

Add a and b, then wrap the result within modulus range

Output

7 + 9 mod 5 = 1

Complexity Analysis

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

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

vs Alternative: Modular arithmetic is much faster than repeated subtraction or division loops for large numbers

Edge Cases

Adding zero

Result is the other number modulo the modulus

DSA Javascript

return (a + b) % this.modulus;

Numbers larger than modulus

Numbers wrap correctly because of modulus operation

DSA Javascript

return (a + b) % this.modulus;

Negative numbers (not handled here)

Result may be negative; additional handling needed for positive remainder

DSA Javascript

return ((a + b) % this.modulus + this.modulus) % this.modulus;

When to Use This Pattern

When you see problems involving wrap-around counting or remainders, use modular arithmetic to keep numbers within a fixed range.

Common Mistakes

Mistake: Forgetting to apply modulus after addition, leading to numbers outside the expected range
Fix: Always apply modulus after arithmetic operations to wrap the result

Summary

It calculates the remainder after division to keep numbers within a fixed range.

Use it when numbers need to wrap around after reaching a limit, like clock hours or cyclic patterns.

The key is to add normally, then apply modulus to wrap the result.

Practice

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

easy

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Understand the modulus operation

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

2. Step 2: Calculate 7 divided by 3

   7 divided by 3 is 2 with a remainder of 1.

3. Final Answer:

   1 -> Option C

4. Quick Check:

   7 % 3 = 1 [OK]

Hint: Modulus gives remainder after division [OK]

Common Mistakes:

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

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

easy

A. a % b

B. a mod b

C. mod(a, b)

D. a // b

Solution

1. Step 1: Recall JavaScript modulus syntax

   In JavaScript, the modulus operator is the percent sign (%) placed between two numbers or variables.

2. Step 2: Identify correct syntax

   Only a % b correctly computes the remainder of a divided by b.

3. Final Answer:

   a % b -> Option A

4. Quick Check:

   Use % for modulus in JavaScript [OK]

Hint: Use % operator for modulus in JavaScript [OK]

Common Mistakes:

• Using 'mod' keyword
• Using integer division operator //
• Calling a non-existent mod() function

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

const x = 15;
const y = 4;
console.log(x % y);

medium

A. 4

B. 3

C. 0

D. 1

Solution

1. Step 1: Calculate 15 divided by 4

   15 divided by 4 is 3 with a remainder of 3.

2. Step 2: Apply modulus operator

   The expression 15 % 4 returns the remainder, which is 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   15 % 4 = 3 [OK]

Hint: Modulus returns remainder after division [OK]

Common Mistakes:

• Confusing remainder with quotient
• Expecting 4 instead of remainder
• Mistaking modulus for division

4. Find the error in the following code snippet that tries to compute the modulus of two numbers:

let a = 10;
let b = 3;
let result = a % b();
console.log(result);

medium

A. Missing semicolon after console.log

B. Modulus operator should be replaced with division

C. Variables a and b should be strings

D. Using parentheses after b causes an error

Solution

1. Step 1: Analyze the modulus expression

   The code uses a % b(), which treats b as a function call, but b is a number, not a function.

2. Step 2: Identify the error

   Parentheses after b cause a runtime error because numbers cannot be called like functions.

3. Final Answer:

   Using parentheses after b causes an error -> Option D

4. Quick Check:

   Variables are not functions, so no () after b [OK]

Hint: Don't add () after variables unless they are functions [OK]

Common Mistakes:

• Adding () after number variables
• Confusing modulus with division
• Ignoring runtime errors

5. You want to find the remainder when the sum of two numbers a = 123456789 and b = 987654321 is divided by 1000. Which expression correctly computes this using modular arithmetic properties?

hard

A. ((a % 1000) + (b % 1000)) % 1000

B. (a % 1000) + (b % 1000)

C. a + b % 1000

D. a % (b % 1000)

Solution

1. Step 1: Recall modular addition property

   The remainder of a sum modulo m equals the sum of remainders modulo m: (a + b) % m = ((a % m) + (b % m)) % m.

2. Step 2: Apply property to given numbers

   Compute (a % 1000) and (b % 1000), add them, then take modulo 1000 again to get correct remainder.

3. Final Answer:

   ((a % 1000) + (b % 1000)) % 1000 -> Option A

4. Quick Check:

   Use modular addition: ((a%m)+(b%m))%m [OK]

Hint: Add remainders then mod again for sum modulus [OK]

Common Mistakes:

• Skipping final modulus after addition
• Adding without modulus
• Using wrong modulus order