Modular Arithmetic Basics in DSA Java - Build from Scratch

Modular Arithmetic Basics

📖 Scenario: Imagine you are working with a clock that only shows hours from 0 to 11. When you add hours, the clock resets after 11 back to 0. This is an example of modular arithmetic.

🎯 Goal: You will create a simple Java program that calculates the result of adding hours on a 12-hour clock using modular arithmetic.

📋 What You'll Learn

Create an integer variable called currentHour with the value 9

Create an integer variable called hoursToAdd with the value 5

Calculate the new hour after adding hoursToAdd to currentHour using modular arithmetic with modulus 12

Print the result stored in a variable called newHour

💡 Why This Matters

🌍 Real World

Modular arithmetic is used in clocks, calendars, cryptography, and computer science to handle repeating cycles.

💼 Career

Understanding modular arithmetic helps in programming tasks involving cycles, hashing, and algorithms that require wrap-around calculations.

1

Create the initial hour variables

Create an integer variable called currentHour and set it to 9. Also create an integer variable called hoursToAdd and set it to 5.

DSA Java

// Create currentHour and hoursToAdd variables
// Your code here

Hint

Use int to create variables and assign the exact values 9 and 5.

2

Add hours using modular arithmetic

Create an integer variable called newHour that stores the result of adding currentHour and hoursToAdd using modular arithmetic with modulus 12. Use the % operator.

DSA Java

public class ModularArithmetic {
    public static void main(String[] args) {
        int currentHour = 9;
        int hoursToAdd = 5;
        // Calculate newHour using modular arithmetic
        // Your code here
    }
}

Hint

Use parentheses to add currentHour and hoursToAdd first, then apply % 12.

3

Print the new hour

Write a System.out.println statement to print the value of newHour.

DSA Java

public class ModularArithmetic {
    public static void main(String[] args) {
        int currentHour = 9;
        int hoursToAdd = 5;
        int newHour = (currentHour + hoursToAdd) % 12;
        // Print newHour
        // Your code here
    }
}

Hint

Use System.out.println to display the value of newHour.

4

Run and check the output

Run the program and observe the printed output. It should show the new hour after adding 5 hours to 9 on a 12-hour clock.

DSA Java

public class ModularArithmetic {
    public static void main(String[] args) {
        int currentHour = 9;
        int hoursToAdd = 5;
        int newHour = (currentHour + hoursToAdd) % 12;
        System.out.println(newHour);
        // Check output
    }
}

Hint

The output should be 2 because 9 + 5 = 14, and 14 % 12 = 2.

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