Why Modular Arithmetic Basics in DSA C++?

The Big Idea

Discover how a simple math trick can fix confusing counting problems like clock hours!

The Scenario

Imagine you are counting hours on a clock. After 12, it goes back to 1. If you try to count hours by just adding numbers without thinking about this wrap-around, you will get wrong times.

The Problem

Simply adding numbers without considering the wrap-around causes confusion and errors. For example, 11 + 3 hours is not 14 but 2 on a 12-hour clock. Doing this manually every time is slow and easy to mess up.

The Solution

Modular arithmetic handles this wrap-around automatically. It keeps numbers within a fixed range by using the remainder after division. This way, calculations like clock hours become simple and error-free.

Before vs After

✗ Before

int time = 11 + 3; // time is 14, but clock shows 2

✓ After

int time = (11 + 3) % 12; // time is 2, correct clock hour

What It Enables

It enables easy and reliable calculations in cycles, like clocks, calendars, and hashing.

Real Life Example

Calculating the day of the week after adding days to a current day uses modular arithmetic to wrap around the 7-day week.

Key Takeaways

Manual addition fails for cyclic counts like clocks.

Modular arithmetic wraps numbers within a fixed range automatically.

This makes cyclic calculations simple and error-free.

Practice

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

easy

A. 5

B. 3

C. 2

D. 0

Solution

1. Step 1: Understand the modulo operation

   The modulo operator (%) gives the remainder after division of the first number 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 C

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 5 instead of remainder
• Ignoring remainder sign

2. Which of the following is the correct syntax to compute the modulo of two integers a and b in C++?

easy

A. a // b

B. a mod b

C. mod(a, b)

D. a % b

Solution

1. Step 1: Recall C++ modulo operator syntax

   In C++, the modulo operator is represented by the percent sign (%).

2. Step 2: Identify correct syntax

   Among the options, only a % b is valid C++ syntax for modulo.

3. Final Answer:

   a % b -> Option D

4. Quick Check:

   C++ uses % for modulo [OK]

Hint: Use % operator for modulo in C++ [OK]

Common Mistakes:

• Using 'mod' keyword
• Using '//' which is floor division in some languages
• Using function call syntax incorrectly

3. What is the output of the following C++ code?

int a = 14;
int b = 4;
int c = (a + b) % 5;
std::cout << c << std::endl;

medium

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Calculate sum inside parentheses

   a + b = 14 + 4 = 18.

2. Step 2: Calculate modulo 5 of the sum

   18 % 5 = 3 because 5 * 3 = 15 and remainder is 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   (14 + 4) % 5 = 18 % 5 = 3 [OK]

Hint: Add first, then modulo [OK]

Common Mistakes:

• Modulo before addition
• Wrong remainder calculation
• Confusing output with sum

4. Identify the error in the following C++ code snippet that tries to compute modulo:

int x = 10;
int y = 0;
int z = x % y;
std::cout << z << std::endl;

medium

A. Syntax error in modulo operator

B. Division by zero error

C. Variable z not declared

D. No error, code runs fine

Solution

1. Step 1: Check modulo divisor value

   The divisor y is 0, which is invalid for modulo operation.

2. Step 2: Understand runtime behavior

   Modulo by zero causes a runtime error (division by zero).

3. Final Answer:

   Division by zero error -> Option B

4. Quick Check:

   Modulo divisor cannot be zero [OK]

Hint: Modulo divisor must not be zero [OK]

Common Mistakes:

• Ignoring zero divisor
• Assuming modulo by zero returns zero
• Confusing syntax error with runtime error

5. Given the expression (a * b) % m, which of the following is a correct way to compute it without causing integer overflow in C++ when a and b can be very large?

hard

A. Use ((a % m) * (b % m)) % m

B. Use (a % m) * (b % m)

C. Use ((long long)a * b) % m

D. Use (a * b) % m directly

Solution

1. Step 1: Understand integer overflow risk

   Multiplying large int values a and b directly can cause undefined behavior due to overflow before % m.

2. Step 2: Safe computation using modulo properties

   Using ((a % m) * (b % m)) % m ensures intermediate values stay within range and prevents overflow.

3. Step 3: Why others fail

   ((long long)a * b) % m may still overflow if b is large and not casted. (a % m) * (b % m) misses final modulo. (a * b) % m overflows.

4. Final Answer:

   ((a % m) * (b % m)) % m -> Option A

5. Quick Check:

   Modulo before multiply and after prevents overflow [OK]

Hint: Apply modulo before and after multiplication to avoid overflow [OK]

Common Mistakes:

• Modulo before multiply without final modulo
• Missing final modulo
• Direct multiplication without modulo