Modular Arithmetic Basics in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Modular Addition

What is the output of the following Java code snippet that performs modular addition?

DSA Java

int a = 17;
int b = 23;
int mod = 10;
int result = (a + b) % mod;
System.out.println(result);

A 0

B 10

C 5

D 1

💡 Hint

Remember to add first, then take the remainder when divided by mod.

Adding 17 and 23 gives 40. Taking 40 modulo 10 gives the remainder 0, so the correct output is 0, option A.

❓ Predict Output

intermediate

Modular Multiplication Result

What will be printed by this Java code that calculates modular multiplication?

DSA Java

int x = 7;
int y = 8;
int mod = 12;
int result = (x * y) % mod;
System.out.println(result);

A 9

B 4

C 8

D 2

💡 Hint

Multiply first, then take the remainder with mod.

7 * 8 = 56. 56 % 12 = 8, so output should be 8. So option C is correct.

🧠 Conceptual

advanced

Properties of Modular Arithmetic

Which of the following statements about modular arithmetic is TRUE?

A Modular multiplication distributes over modular addition.

B Modular subtraction always produces a positive result.

C Modular addition is not associative.

D Modular division is always defined for any divisor.

💡 Hint

Think about how multiplication and addition behave under modulus.

Modular multiplication distributes over modular addition: (a * (b + c)) % m = ((a * b) % m + (a * c) % m) % m. Modular addition is associative, so A is false. Modular subtraction can produce negative results before taking modulus, so C is false. Modular division is not always defined because inverse may not exist, so D is false.

🔧 Debug

advanced

Identify the Error in Modular Exponentiation Code

What error does this Java code produce when trying to compute (base^exp) % mod?

DSA Java

int base = 3;
int exp = 4;
int mod = 5;
int result = 1;
for (int i = 0; i < exp; i++) {
    result = (result * base) / mod;
}
System.out.println(result);

A Syntax error due to missing semicolon.

B Throws ArithmeticException due to division by zero.

C Compiles but infinite loop occurs.

D Prints incorrect result due to wrong operator.

💡 Hint

Check the operator used for modular reduction inside the loop.

The code uses division '/' instead of modulus '%' to reduce the result. This causes incorrect calculation but no runtime error. So option D is correct.

🚀 Application

expert

Number of Distinct Values in Modular Sequence

Given the Java code below, how many distinct values will be printed?

DSA Java

int mod = 7;
Set<Integer> values = new HashSet<>();
for (int i = 0; i < 20; i++) {
    int val = (3 * i) % mod;
    values.add(val);
}
System.out.println(values.size());

A 6

B 7

C 20

D 3

💡 Hint

Consider the properties of multiplication modulo a prime number.

Since 3 and 7 are coprime, multiplying by 3 modulo 7 cycles through all residues 0 to 6. So all 7 distinct values appear.

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