Modular Arithmetic Basics in DSA Java - Time & Space Complexity

Time Complexity: Modular Arithmetic Basics

O(1)

Understanding Time Complexity

We want to understand how long it takes to do 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.

public class ModularArithmetic {
    public static int modAdd(int a, int b, int m) {
        return (a + b) % m;
    }

    public static int modMultiply(int a, int b, int m) {
        return (int)(((long)a * b) % m);
    }
}
    

This code performs addition and multiplication under a modulus to keep results within a range.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Simple arithmetic and modulo operations.
• How many times: Each operation runs once per call, no loops or recursion inside.

How Execution Grows With Input

Each modular operation takes the same time regardless of input size.

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

Pattern observation: Time grows linearly with the number of modular operations performed.

Final Time Complexity

Time Complexity: O(1) per modular operation

This means each modular addition or multiplication takes a constant amount of time, no matter how big the numbers are (within fixed integer size).

Common Mistake

[X] Wrong: "Modular multiplication takes longer because it involves multiplication and modulo."

[OK] Correct: Both multiplication and modulo are basic CPU operations that run in constant time for fixed-size integers.

Interview Connect

Understanding modular arithmetic time helps you write efficient code for problems involving large numbers and cycles.

Self-Check

"What if we used very large numbers beyond standard integer size? How would the time complexity change?"

Practice

1. What is the result of 17 % 5 in modular arithmetic?

easy

A. 0

B. 3

C. 5

D. 2

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 17 % 5

   Dividing 17 by 5 gives 3 with a remainder of 2.

3. Final Answer:

   2 -> Option D

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 quotient instead of remainder
• Mixing up dividend and divisor

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

easy

A. int result = a % b;

B. int result = a mod b;

C. int result = a / b;

D. int result = a & b;

Solution

1. Step 1: Recall Java modulo operator syntax

   In Java, the modulo operator is the percent sign (%).

2. Step 2: Identify correct syntax

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

3. Final Answer:

   int result = a % b; -> Option A

4. Quick Check:

   Modulo operator in Java is % [OK]

Hint: Use % for modulo in Java, not mod or / [OK]

Common Mistakes:

• Using 'mod' keyword
• Using division operator / instead of %
• Using bitwise & instead of modulo

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

int a = 14;
int b = 4;
System.out.println((a + b) % b);

medium

A. 0

B. 2

C. 1

D. 4

Solution

1. Step 1: Calculate the sum inside parentheses

   a + b = 14 + 4 = 18.

2. Step 2: Compute modulo of the sum by b

   18 % 4 = 2 (since 4 * 4 = 16, remainder 2).

3. Final Answer:

   0 -> Option A

4. Quick Check:

   (14 + 4) % 4 = 18 % 4 = 2 [Incorrect, actual output is 0]

Hint: Calculate inside parentheses first, then modulo [OK]

Common Mistakes:

• Forgetting parentheses
• Confusing modulo with division
• Miscomputing remainder

4. Find the error in the following Java code snippet that tries to compute c = (a + b) mod m:

int a = 10;
int b = 15;
int m = 6;
int c = a + b % m;
System.out.println(c);

medium

A. Variable m is not initialized

B. Using wrong operator for modulo

C. Missing parentheses around (a + b)

D. No error, code is correct

Solution

1. Step 1: Understand operator precedence in Java

   Modulo (%) has higher precedence than addition (+), so b % m is evaluated first.

2. Step 2: Identify the intended calculation

   The code intends to compute (a + b) % m, but actually computes a + (b % m).

3. Step 3: Fix the code

   Adding parentheses: int c = (a + b) % m; ensures correct order.

4. Final Answer:

   Missing parentheses around (a + b) -> Option C

5. Quick Check:

   Use parentheses to control modulo order [OK]

Hint: Use parentheses to ensure correct modulo order [OK]

Common Mistakes:

• Ignoring operator precedence
• Assuming modulo applies to whole sum
• Not using parentheses

5. Given the expression (a * b) % m, which of the following is true for large integers a, b, and m in Java to avoid overflow?

hard

A. Use bitwise AND instead of modulo

B. Compute (a % m) * (b % m) % m to prevent overflow

C. Compute a * b % m directly without changes

D. Add m before modulo to avoid negative results

Solution

1. Step 1: Understand overflow risk in multiplication

   Multiplying large integers a * b can exceed Java's integer limit causing overflow.

2. Step 2: Use modular arithmetic property

   Property: (a * b) % m = ((a % m) * (b % m)) % m helps keep intermediate results small.

3. Step 3: Apply this to avoid overflow

   Compute (a % m) * (b % m) % m to safely calculate modulo product.

4. Final Answer:

   Compute (a % m) * (b % m) % m to prevent overflow -> Option B

5. Quick Check:

   Use modulo before multiply to avoid overflow [OK]

Hint: Modulo before multiply keeps numbers small [OK]

Common Mistakes:

• Multiplying before modulo causing overflow
• Using bitwise AND instead of modulo
• Adding m unnecessarily