Modular Arithmetic Basics in DSA Javascript - Time & Space Complexity

Time Complexity: Modular Arithmetic Basics

O(n)

Understanding Time Complexity

We want to understand how long it takes to perform modular arithmetic operations in code.

Specifically, how the time grows when we do many modular calculations.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function modAdd(a, b, m) {
  return (a + b) % m;
}

function modMultiply(a, b, m) {
  return (a * b) % m;
}

// Using modAdd and modMultiply in a loop
function sumModArray(arr, m) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum = modAdd(sum, arr[i], m);
  }
  return sum;
}
    

This code performs modular addition and multiplication, then sums an array with modular addition.

Identify Repeating Operations

• Primary operation: The loop in sumModArray that adds each element modulo m.
• How many times: The loop runs once for each element in the array, so n times where n is the array length.

How Execution Grows With Input

Each element requires one modular addition operation, so the total work grows directly with the number of elements.

Input Size (n)	Approx. Operations
10	10 modular additions
100	100 modular additions
1000	1000 modular additions

Pattern observation: The operations increase linearly as input size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the modular sum grows in direct proportion to the number of elements.

Common Mistake

[X] Wrong: "Modular operations take more time as numbers get bigger, so complexity depends on number size too."

[OK] Correct: Modular arithmetic operations are constant time for fixed-size numbers in typical programming languages, so complexity depends mainly on how many operations we do, not the size of the numbers.

Interview Connect

Understanding modular arithmetic time complexity helps you reason about algorithms that use it, like hashing or cryptography, showing you can analyze how your code scales.

Self-Check

"What if we replaced the loop with a recursive function that sums the array modulo m? How would the time complexity change?"

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