Why Modular Arithmetic Basics in DSA Java?

The Big Idea

What if you never had to worry about numbers going beyond limits again?

The Scenario

Imagine you are trying to keep track of hours on a clock. If you add hours manually without resetting after 12, you get confusing numbers like 13, 14, or 25, which don't make sense on a clock face.

The Problem

Manually adjusting numbers every time they go beyond 12 is slow and error-prone. You might forget to reset, causing wrong results and confusion.

The Solution

Modular arithmetic automatically wraps numbers around a fixed limit, like a clock resets after 12 hours. This keeps numbers within a range and simplifies calculations.

Before vs After

✗ Before

int hour = 10;
hour = hour + 5; // hour becomes 15, which is invalid on a 12-hour clock
if (hour > 12) {
  hour = hour - 12; // manual reset
}

✓ After

int hour = 10;
hour = (hour + 5) % 12; // hour becomes 3 automatically
if (hour == 0) {
  hour = 12; // adjust for 12-hour clock representation
}

What It Enables

It enables easy handling of repeating cycles and keeps numbers within a fixed range without extra checks.

Real Life Example

Calculating the day of the week after adding days to a current day, where the week cycles every 7 days.

Key Takeaways

Manual counting beyond limits causes errors and confusion.

Modular arithmetic wraps numbers within a fixed range automatically.

This simplifies calculations involving cycles like clocks and calendars.

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