Modular Arithmetic Basics in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Modular Addition

What is the output of this Rust code that performs modular addition?

DSA Rust

fn main() {
    let a = 17;
    let b = 29;
    let m = 10;
    let result = (a + b) % m;
    println!("{}", result);
}

A 0

B 6

C 16

D 7

💡 Hint

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

The sum is 17 + 29 = 46. Taking 46 modulo 10 gives 6 because 46 divided by 10 leaves a remainder of 6.

❓ Predict Output

intermediate

Modular Multiplication Result

What does this Rust program print after performing modular multiplication?

DSA Rust

fn main() {
    let x = 7;
    let y = 8;
    let m = 12;
    let result = (x * y) % m;
    println!("{}", result);
}

A 8

B 4

C 56

D 0

💡 Hint

Multiply first, then find remainder after dividing by modulus.

7 * 8 = 56. 56 % 12 = 8 because 12 * 4 = 48 and 56 - 48 = 8.

❓ Predict Output

advanced

Modular Exponentiation Output

What is the output of this Rust code that calculates modular exponentiation?

DSA Rust

fn main() {
    let base = 3u64;
    let exponent = 4u64;
    let modulus = 5u64;
    let mut result = 1u64;
    for _ in 0..exponent {
        result = (result * base) % modulus;
    }
    println!("{}", result);
}

A 1

B 2

C 3

D 4

💡 Hint

Calculate 3^4 mod 5 step by step.

3^1 mod 5 = 3

3^2 mod 5 = 9 mod 5 = 4

3^3 mod 5 = 4 * 3 = 12 mod 5 = 2

3^4 mod 5 = 2 * 3 = 6 mod 5 = 1

But the code multiplies 4 times starting from 1, so final result is 1.

Re-check the loop: result starts at 1, multiply by 3 mod 5 four times:

Iteration 1: 1*3=3 mod5=3

Iteration 2: 3*3=9 mod5=4

Iteration 3: 4*3=12 mod5=2

Iteration 4: 2*3=6 mod5=1

Final result is 1.

🔧 Debug

advanced

Identify the Error in Modular Inverse Code

What error will this Rust code produce when trying to compute modular inverse using Extended Euclidean Algorithm?

DSA Rust

fn mod_inverse(a: i64, m: i64) -> i64 {
    let mut m0 = m;
    let mut y = 0;
    let mut x = 1;
    let mut a = a;
    if m == 1 {
        return 0;
    }
    while a > 1 {
        let q = a / m0;
        let mut t = m0;
        m0 = a % m0;
        a = t;
        t = y;
        y = x - q * y;
        x = t;
    }
    if x < 0 {
        x += m;
    }
    x
}

fn main() {
    println!("{}", mod_inverse(3, 11));
}

A Infinite loop

B Runtime panic due to division by zero

C Correct output: 4

D Compile-time error due to variable shadowing

💡 Hint

Trace the execution for inputs 3 and 11.

The code correctly computes the modular inverse of 3 modulo 11 using the Extended Euclidean Algorithm. The inverse is 4 because 3 * 4 = 12 ≡ 1 (mod 11). No error occurs for coprime inputs like these.

🧠 Conceptual

expert

Properties of Modular Arithmetic

Which of the following statements about modular arithmetic is always true for integers a, b, and modulus m > 1?

A (a / b) mod m = ((a mod m) / (b mod m)) mod m

B (a - b) mod m = ((a mod m) - (b mod m)) mod m

C (a * b) mod m = ((a mod m) * (b mod m)) mod m

D (a + b) mod m = ((a mod m) + (b mod m)) mod m

💡 Hint

Recall which operations distribute over modulo.

Addition and multiplication distribute over modulo, but subtraction can cause negative results and division is not generally defined in modular arithmetic without modular inverse.

Practice

1. What is the result of 7 % 3 in modular arithmetic?

easy

A. 2

B. 1

C. 3

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 7 modulo 3

   7 divided by 3 is 2 with a remainder of 1, so 7 % 3 = 1.

3. Final Answer:

   1 -> Option A

4. Quick Check:

   7 % 3 = 1 [OK]

Hint: Modulo gives remainder after division [OK]

Common Mistakes:

• Confusing modulo with division
• Using 3 instead of remainder
• Thinking modulo returns quotient

2. Which of the following is the correct Rust syntax to compute the remainder of 15 divided by 4?

easy

A. let result = 15 / 4;

B. let result = 15 mod 4;

C. let result = 15 % 4;

D. let result = 15 rem 4;

Solution

1. Step 1: Recall Rust modulo syntax

   In Rust, the modulo operator is the percent sign (%), not 'mod' or 'rem'.

2. Step 2: Identify correct syntax

   let result = 15 % 4; uses % correctly: let result = 15 % 4;

3. Final Answer:

   let result = 15 % 4; -> Option C

4. Quick Check:

   Rust uses % for modulo [OK]

Hint: Use % operator for modulo in Rust [OK]

Common Mistakes:

• Using 'mod' keyword incorrectly
• Using division operator instead of modulo
• Using 'rem' which is invalid syntax

3. What is the output of the following Rust code?

fn main() {
    let a = 10;
    let b = 6;
    let c = (a + b) % 7;
    println!("{}", c);
}

medium

A. 4

B. 2

C. 3

D. 1

Solution

1. Step 1: Calculate sum inside parentheses

   a + b = 10 + 6 = 16.

2. Step 2: Compute modulo 7 of the sum

   16 % 7 = 2 (because 7 * 2 = 14, remainder 2).

3. Step 3: Check printed output

   The code prints the value of c, which is 2.

4. Final Answer:

   2 -> Option B

5. Quick Check:

   (10 + 6) % 7 = 2 [OK]

Hint: Calculate sum first, then modulo [OK]

Common Mistakes:

• Modulo before addition
• Wrong remainder calculation
• Confusing modulo with division

4. Identify the error in this Rust code snippet that tries to compute modulo:

fn main() {
    let x = 20;
    let y = 0;
    let z = x % y;
    println!("{}", z);
}

medium

A. Division by zero error at runtime

B. Syntax error: % operator not allowed

C. Variable y is not initialized

D. No error, code runs fine

Solution

1. Step 1: Analyze modulo operation with zero divisor

   Modulo by zero is undefined and causes a runtime error in Rust.

2. Step 2: Identify error type

   The code will compile but panic at runtime due to division by zero.

3. Final Answer:

   Division by zero error at runtime -> Option A

4. Quick Check:

   Modulo by zero causes runtime panic [OK]

Hint: Never modulo by zero; causes runtime panic [OK]

Common Mistakes:

• Thinking it's a syntax error
• Ignoring zero divisor
• Assuming code runs fine

5. You want to compute (a * b) % m for very large integers a and b in Rust without overflow. Which approach is best?

hard

A. Compute a * b first, then modulo m

B. Convert numbers to strings and then modulo

C. Use floating point multiplication and then modulo

D. Use modular multiplication: ((a % m) * (b % m)) % m

Solution

1. Step 1: Understand overflow risk

   Multiplying large integers directly can overflow before modulo is applied.

2. Step 2: Apply modular multiplication property

   Using ((a % m) * (b % m)) % m keeps intermediate values small and avoids overflow.

3. Step 3: Evaluate other options

   Compute a * b first, then modulo m risks overflow; options B and C are invalid or inefficient.

4. Final Answer:

   Use modular multiplication: ((a % m) * (b % m)) % m -> Option D

5. Quick Check:

   (a * b) % m = ((a % m) * (b % m)) % m [OK]

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

Common Mistakes:

• Multiplying before modulo causing overflow
• Using floats incorrectly
• String conversion misuse