Modular Arithmetic Basics in DSA Go

Mental Model

Modular arithmetic means working with numbers that wrap around after reaching a certain value, like a clock resets after 12 hours.

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

Numbers: 0 -> 1 -> 2 -> ... -> M-1 -> back to 0 (wrap around)
Example with M=5:
0 -> 1 -> 2 -> 3 -> 4 -> [wraps back to 0]

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 normally before applying the modulo

Step 2: Divide 16 by 5 and find the remainder

16 ÷ 5 = 3 remainder 1

Why: Modulo means taking the remainder after division

Step 3: Result is the remainder 1

(7 + 9) mod 5 = 1

Why: The final answer is the remainder after division

Result:

(7 + 9) mod 5 = 1

Annotated Code

DSA Go

package main

import "fmt"

// modAdd returns (a + b) mod m
func modAdd(a, b, m int) int {
    sum := a + b
    // wrap sum around modulo m
    result := sum % m
    return result
}

func main() {
    a, b, m := 7, 9, 5
    res := modAdd(a, b, m)
    fmt.Printf("(%d + %d) mod %d = %d\n", a, b, m, res)
}

sum := a + b

Add the two numbers first

result := sum % m

Calculate remainder after division by m

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

When a or b is zero

The function correctly returns the modulo of the non-zero number

DSA Go

result := sum % m

When a or b is larger than m

The sum can be larger than m but modulo wraps it correctly

DSA Go

result := sum % m

When m is 1

Result is always 0 because any number mod 1 is 0

DSA Go

result := sum % m

When to Use This Pattern

When you see problems involving wrapping numbers or remainders, use modular arithmetic to simplify calculations and avoid large numbers.

Common Mistakes

Mistake: Forgetting to apply modulo after addition, leading to incorrect large results
Fix: Always apply modulo operation after arithmetic to keep numbers within range

Summary

Modular arithmetic calculates remainders after division, wrapping numbers around a fixed range.

Use it when you need to keep numbers within a cycle or range, like clock hours or hashing.

The key insight is that numbers reset after reaching the modulo value, just like a clock resets after 12.

Practice

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

easy

A. 0

B. 2

C. 1

D. 3

Solution

1. Step 1: Understand the modulus operation

   The modulus operator (%) gives the remainder when the first number is divided by the second.

2. Step 2: Calculate 7 % 3

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

3. Final Answer:

   1 -> Option C

4. Quick Check:

   7 % 3 = 1 [OK]

Hint: Modulus gives remainder after division [OK]

Common Mistakes:

• Confusing modulus with division
• Using quotient instead of remainder
• Mixing up operands order

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

easy

A. mod := a % b

B. mod := a mod b

C. mod := a %% b

D. mod := a mod(b)

Solution

1. Step 1: Recall Go syntax for modulus

   In Go, the modulus operator is the percent sign (%) used between two integers.

2. Step 2: Identify correct syntax

   mod := a % b uses a % b, which is the correct way to compute modulus in Go.

3. Final Answer:

   mod := a % b -> Option A

4. Quick Check:

   Go uses % for modulus [OK]

Hint: Use % operator for modulus in Go [OK]

Common Mistakes:

• Using 'mod' keyword instead of %
• Double percent signs %%
• Using function call syntax for modulus

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

package main
import "fmt"
func main() {
    a := 14
    b := 5
    fmt.Println(a % b)
}

medium

A. 2

B. 4

C. 3

D. 0

Solution

1. Step 1: Understand the code variables

   Variable a is 14 and b is 5.

2. Step 2: Calculate 14 % 5

   14 divided by 5 is 2 with remainder 4, so output is 4.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   14 % 5 = 4 [OK]

Hint: Divide and find remainder for modulus [OK]

Common Mistakes:

• Using division result instead of remainder
• Confusing operands order
• Misreading variable values

4. Find the error in this Go code snippet that tries to compute modulus:

package main
import "fmt"
func main() {
    var a, b int = 10, 3
    result := a mod b
    fmt.Println(result)
}

medium

A. Missing import for modulus package

B. fmt.Println syntax error

C. Variables a and b not declared

D. Using 'mod' instead of '%' operator

Solution

1. Step 1: Check modulus operator usage

   The code uses a mod b, but Go does not have a 'mod' keyword.

2. Step 2: Correct operator in Go

   Go uses the percent sign (%) for modulus, so it should be a % b.

3. Final Answer:

   Using 'mod' instead of '%' operator -> Option D

4. Quick Check:

   Modulus in Go uses % [OK]

Hint: Use % operator, not 'mod' keyword [OK]

Common Mistakes:

• Using 'mod' keyword
• Assuming modulus needs import
• Incorrect variable declaration assumptions

5. You want to find the remainder when the sum of two large numbers a = 123456789 and b = 987654321 is divided by 1000. Which expression correctly uses modular arithmetic to compute this efficiently in Go?

hard

A. (a % 1000 + b % 1000) % 1000

B. (a + b) / 1000

C. a % 1000 + b % 1000

D. a + b % 1000

Solution

1. Step 1: Understand modular addition property

   Modular arithmetic allows (a + b) % m = ((a % m) + (b % m)) % m to avoid large sums.

2. Step 2: Apply property to given numbers

   Compute (a % 1000 + b % 1000) % 1000 to get remainder without overflow.

3. Final Answer:

   (a % 1000 + b % 1000) % 1000 -> Option A

4. Quick Check:

   (a + b) % 1000 = ((a % 1000) + (b % 1000)) % 1000 [OK]

Hint: Use modular addition to avoid big sums [OK]

Common Mistakes:

• Adding remainders without final modulus
• Not applying modulus before addition
• Misplacing parentheses