Modular Arithmetic Basics in DSA C#

Mental Model

Modular arithmetic means counting numbers but wrapping around after reaching a certain value, like a clock resets after 12.

Analogy: Think of a clock showing hours from 1 to 12. After 12, it goes back to 1. This wrapping around is modular arithmetic.

Clock: 1 -> 2 -> 3 -> ... -> 11 -> 12 -> 1 (wraps around)
Number line mod 5: 0 -> 1 -> 2 -> 3 -> 4 -> 0 (wraps around)

Dry Run Walkthrough

Input: Calculate (7 + 9) mod 5

Goal: Find the remainder when the sum of 7 and 9 is divided by 5

Step 1: Add 7 and 9 to get 16

Sum = 16

Why: We first add the numbers before applying the modulo

Step 2: Divide 16 by 5 and find the remainder

16 ÷ 5 = 3 remainder 1

Why: Modulo gives the remainder after division

Step 3: Result is the remainder 1

16 mod 5 = 1

Why: This is the wrapped-around value on the number line mod 5

Result:

1

Annotated Code

DSA C#

using System;

class ModularArithmetic
{
    // Function to compute (a + b) mod m
    public static int AddMod(int a, int b, int m)
    {
        int sum = a + b; // add the two numbers
        int result = sum % m; // find remainder after division by m
        if (result < 0) result += m; // handle negative results
        return result; // return the modular sum
    }

    static void Main()
    {
        int a = 7, b = 9, m = 5;
        int modSum = AddMod(a, b, m);
        Console.WriteLine($"({a} + {b}) mod {m} = {modSum}");
    }
}

int sum = a + b; // add the two numbers

Add the input numbers before applying modulo

int result = sum % m; // find remainder after division by m

Calculate remainder to wrap around the modulus

if (result < 0) result += m; // handle negative results

Adjust negative remainder to positive equivalent

return result; // return the modular sum

Return the final modular arithmetic result

Output

(7 + 9) mod 5 = 1

Complexity Analysis

Time: O(1) because addition and modulo operations take constant time

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Modular arithmetic is much faster and simpler than repeated subtraction or division to find remainders

Edge Cases

Negative numbers as input

The code adjusts negative modulo results to positive values within the modulus range

DSA C#

if (result < 0) result += m; // handle negative results

Zero modulus (m = 0)

Division by zero error occurs; code does not handle this case explicitly

When to Use This Pattern

When you see problems asking for results 'mod' some number, use modular arithmetic to keep numbers within a fixed range and avoid overflow.

Common Mistakes

Mistake: Not handling negative results after modulo operation
Fix: Add modulus to negative results to get correct positive remainder

Mistake: Using modulo with zero as modulus
Fix: Ensure modulus is never zero before performing modulo operation

Summary

It calculates the remainder after division to keep numbers within a fixed range.

Use it when you want to wrap numbers around a limit, like clock hours or cyclic patterns.

Remember that modulo wraps numbers around and negative results must be adjusted to positive.

Practice

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

easy

A. 2

B. 3

C. 5

D. 0

Solution

1. Step 1: Understand the modulus operation

   The modulus 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 A

4. Quick Check:

   17 % 5 = 2 [OK]

Hint: Modulus gives remainder after division [OK]

Common Mistakes:

• Confusing modulus with division result
• Using quotient instead of remainder
• Thinking modulus returns zero if not divisible

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

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 C# modulus operator

   In C#, the modulus operator is the percent sign (%).

2. Step 2: Check each option

   int result = a % b; uses % correctly. int result = a mod b; uses 'mod' which is not valid syntax. int result = a / b; uses division (/), not modulus. int result = a & b; uses bitwise AND (&), unrelated to modulus.

3. Final Answer:

   int result = a % b; -> Option D

4. Quick Check:

   C# modulus syntax = a % b [OK]

Hint: Use % symbol for modulus in C# [OK]

Common Mistakes:

• Using 'mod' keyword instead of %
• Confusing division (/) with modulus (%)
• Using bitwise operators (&) mistakenly

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

int a = 14;
int b = 4;
int c = (a + b) % 5;
Console.WriteLine(c);

medium

A. 2

B. 4

C. 3

D. 1

Solution

1. Step 1: Calculate sum inside parentheses

   a + b = 14 + 4 = 18.

2. Step 2: Compute modulus 18 % 5

   18 divided by 5 is 3 remainder 3, so 18 % 5 = 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

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

Hint: Add first, then apply modulus [OK]

Common Mistakes:

• Applying modulus before addition
• Confusing remainder with quotient
• Incorrect arithmetic calculation

4. Identify the error in the following C# code snippet that tries to compute modulus:

int x = 10;
int y = 3;
int result = x % y;

medium

A. No error, code is correct

B. Missing semicolon after the first line

C. Using % operator with integers is invalid

D. Variables x and y must be declared as double

Solution

1. Step 1: Check syntax correctness

   Each line ends with a semicolon; variables are declared as integers.

2. Step 2: Validate modulus usage

   The modulus operator (%) works correctly with integers in C#.

3. Final Answer:

   No error, code is correct -> Option A

4. Quick Check:

   Modulus with int variables is valid [OK]

Hint: Modulus works with int types and needs semicolons [OK]

Common Mistakes:

• Thinking % is invalid for integers
• Missing semicolons (not in this code)
• Using floating types unnecessarily

5. You want to find the remainder when the sum of all numbers from 1 to 100 is divided by 7. Which C# expression correctly computes this using modular arithmetic?

hard

A. int result = 100 * (101 % 7) / 2;

B. int result = (100 * 101 / 2) % 7;

C. int result = (100 % 7) * (101 % 7) / 2;

D. int result = (100 + 101) % 7 / 2;

Solution

1. Step 1: Recall formula for sum 1 to n

   The sum of numbers from 1 to 100 is n(n+1)/2 = 100*101/2.

2. Step 2: Apply modulus after full sum calculation

   Compute (100*101/2) % 7 to get the remainder after division by 7.

3. Final Answer:

   int result = (100 * 101 / 2) % 7; -> Option B

4. Quick Check:

   Sum formula then modulus = correct [OK]

Hint: Calculate full sum first, then apply modulus [OK]

Common Mistakes:

• Applying modulus before multiplication or division
• Incorrect order of operations
• Dividing before multiplying causing wrong result