Modular Arithmetic Basics in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Modular Addition

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

DSA C++

int a = 17;
int b = 25;
int mod = 10;
int result = (a + b) % mod;
std::cout << result << std::endl;

A 7

B 0

C 12

D 2

💡 Hint

Remember to add first, then take the remainder with the modulus.

17 + 25 = 42. 42 % 10 = 2.

❓ Predict Output

intermediate

Output of Modular Multiplication

What is the output of this C++ code that calculates modular multiplication?

DSA C++

int a = 7;
int b = 8;
int mod = 5;
int result = (a * b) % mod;
std::cout << result << std::endl;

A 1

B 6

C 0

D 3

💡 Hint

Multiply first, then take the remainder.

7 * 8 = 56. 56 % 5 = 1.

❓ Predict Output

advanced

Modular Exponentiation Output

What is the output of this C++ code that computes modular exponentiation using a loop?

DSA C++

int base = 3;
int exponent = 4;
int mod = 7;
int result = 1;
for(int i = 0; i < exponent; i++) {
    result = (result * base) % mod;
}
std::cout << result << std::endl;

A 2

B 4

C 1

D 5

💡 Hint

Calculate 3^4 mod 7 step by step.

3^4 = 81. 81 % 7 = 4.

🧠 Conceptual

advanced

Understanding Modular Inverse

Which of the following statements about modular inverse is correct when modulus is a prime number?

A Modular inverse of a number a exists only if a is less than modulus divided by 2.

B Modular inverse of a number a always exists regardless of modulus.

C Modular inverse of a number a exists if and only if a and modulus are coprime.

D Modular inverse of a number a exists only if a is even.

💡 Hint

Think about the properties of prime modulus and coprimality.

When modulus is prime, every number except multiples of modulus has an inverse because they are coprime.

🔧 Debug

expert

Identify the Error in Modular Exponentiation Code

What error will this C++ code produce when computing modular exponentiation?

DSA C++

int mod_exp(int base, int exponent, int mod) {
    int result = 1;
    while (exponent) {
        if (exponent & 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exponent = exponent >> 1;
    }
    return result;
}

int main() {
    std::cout << mod_exp(2, -3, 5) << std::endl;
    return 0;
}

A Infinite loop due to negative exponent

B Runs but outputs 0

C Runs correctly and outputs 3

D Compilation error due to bitwise operations on int

💡 Hint

Consider what happens when exponent is negative in the while loop condition.

The while (exponent) condition (i.e., exponent != 0) is true for negative values. Right-shifting negative signed integers (implementation-defined behavior) typically preserves the sign bit, preventing exponent from reaching zero and causing an infinite loop.

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