Modular Arithmetic Basics in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is modular arithmetic?

Modular arithmetic is a way of doing math where numbers wrap around after reaching a certain value called the modulus. Think of a clock where after 12 comes 1 again.

beginner

What does the expression 'a % m' mean in modular arithmetic?

It means the remainder when number 'a' is divided by 'm'. For example, 17 % 5 equals 2 because 17 divided by 5 leaves a remainder of 2.

beginner

How do addition and multiplication work under modular arithmetic?

Addition and multiplication under modular arithmetic work like normal but the result is taken modulo the modulus. For example, (7 + 8) % 5 = 0 and (4 * 3) % 5 = 2.

intermediate

Why is modular arithmetic useful in programming?

It helps keep numbers within a fixed range, avoids overflow, and is used in hashing, cryptography, and algorithms that need wrap-around behavior.

intermediate

What is the result of (a - b) % m if (a - b) is negative?

If (a - b) is negative, adding the modulus 'm' to it will give a positive equivalent. For example, (3 - 5) % 7 = (-2) % 7 = 5.

What is 14 % 4?

A 2

B 3

C 4

D 1

14 divided by 4 is 3 with remainder 2, so 14 % 4 = 2.

What is (9 + 8) % 7?

A 2

B 3

C 4

D 5

9 + 8 = 17, 17 % 7 = 3.

Which of these is true for modular multiplication?

A (a * b) % m = ((a % m) * (b % m)) % m

B (a * b) % m = (a + b) % m

C (a * b) % m = (a - b) % m

D (a * b) % m = a % b

Modular multiplication distributes over modulus: (a * b) % m = ((a % m) * (b % m)) % m.

If a = 5, b = 9, and m = 7, what is (a - b) % m?

A 6

B 1

C 3

D 5

5 - 9 = -4, -4 % 7 = 3 (if negative, add 7), so 3 is correct. But since 3 is option A, correct answer is A.

Why do we use modular arithmetic in hashing?

A To sort data quickly

B To increase the size of hash values

C To avoid collisions completely

D To keep hash values within a fixed range

Modular arithmetic keeps hash values within a fixed range, which helps in indexing.

Explain modular addition and how it differs from normal addition.

Think about how a clock resets after 12.

Describe how to handle negative results in modular subtraction.

What do you do if the remainder is negative?

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