Modular Arithmetic Basics in DSA Java

Mental Model

Modular arithmetic means working with numbers wrapped 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 (7 * 5) mod 10

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

Step 1: Add 7 and 5 to get 12

Sum = 12

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

Step 2: Apply modulus 10 to sum: 12 mod 10 = 2

Result = 2

Why: Wrap around to keep result within 0 to 9

Step 3: Multiply 7 and 5 to get 35

Product = 35

Why: We do normal multiplication before applying the wrap-around

Step 4: Apply modulus 10 to product: 35 mod 10 = 5

Result = 5

Why: Wrap around to keep result within 0 to 9

Result:

Addition result: 2
Multiplication result: 5

Annotated Code

DSA Java

public class ModularArithmetic {
    // Function to perform modular addition
    public static int modAdd(int a, int b, int mod) {
        int sum = a + b; // normal addition
        return sum % mod; // wrap around using modulus
    }

    // Function to perform modular multiplication
    public static int modMultiply(int a, int b, int mod) {
        int product = a * b; // normal multiplication
        return product % mod; // wrap around using modulus
    }

    public static void main(String[] args) {
        int a = 7;
        int b = 5;
        int mod = 10;

        int addResult = modAdd(a, b, mod);
        int multiplyResult = modMultiply(a, b, mod);

        System.out.println("Addition result: " + addResult);
        System.out.println("Multiplication result: " + multiplyResult);
    }
}

int sum = a + b; // normal addition

Add two numbers normally before wrapping

return sum % mod; // wrap around using modulus

Apply modulus to keep result within range

int product = a * b; // normal multiplication

Multiply two numbers normally before wrapping

return product % mod; // wrap around using modulus

Apply modulus to keep result within range

Output

Addition result: 2

Multiplication result: 5

Complexity Analysis

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

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

vs Alternative: Modular arithmetic is faster and simpler than handling large numbers directly because it keeps results small and manageable

Edge Cases

Operands equal to zero

Addition or multiplication with zero correctly returns zero modulo the modulus

DSA Java

int sum = a + b; // normal addition

Operands larger than modulus

Operands larger than modulus still produce correct wrapped results due to modulus operation

DSA Java

return sum % mod; // wrap around using modulus

Modulus is 1

All results become zero because any number mod 1 is zero

DSA Java

return sum % mod; // wrap around using modulus

When to Use This Pattern

When you see problems involving wrapping numbers around a fixed range or dealing with large numbers that need to stay small, reach for modular arithmetic because it keeps numbers manageable and predictable.

Common Mistakes

Mistake: Applying modulus only after addition but not after multiplication
Fix: Always apply modulus after every arithmetic operation to keep results within range

Mistake: Using negative numbers without adjusting modulus result
Fix: Ensure modulus result is non-negative by adding modulus if result is negative

Summary

Modular arithmetic wraps numbers around after reaching a fixed modulus value.

Use it when you want to keep numbers within a limited range, like clock hours or large number computations.

The key insight is that after normal addition or multiplication, applying modulus keeps results small and predictable.

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