Modular Arithmetic Basics in DSA Go - 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. It's like a clock where after 12 comes 1 again.

beginner

What does the expression 'a mod n' mean?

'a mod n' means the remainder when number 'a' is divided by 'n'. For example, 17 mod 5 is 2 because 17 divided by 5 leaves a remainder of 2.

beginner

How do addition and multiplication work in modular arithmetic?

In modular arithmetic, you add or multiply numbers normally, then take the remainder after dividing by the modulus. For example, (7 + 8) mod 5 = 15 mod 5 = 0.

intermediate

Why is modular arithmetic useful in programming?

Modular arithmetic helps keep numbers within a fixed range, which is useful for things like hashing, cryptography, and avoiding overflow in calculations.

intermediate

What is the result of (a - b) mod n if a < b?

If a < b, (a - b) mod n is calculated by adding n to (a - b) before taking the modulus. This keeps the result positive within the range 0 to n-1.

What is 14 mod 4?

A 3

B 2

C 1

D 0

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

What is (9 + 7) mod 5?

A 2

B 0

C 4

D 1

9 + 7 = 16, 16 mod 5 = 1 remainder 1, so answer is 1.

Which of these is true for modular arithmetic?

A (a * b) mod n = (a * b)

B (a + b) mod n = (a + b)

C (a + b) mod n = ((a mod n) + (b mod n)) mod n

D (a - b) mod n = (b - a) mod n

Modular addition can be broken down as (a mod n + b mod n) mod n.

If n = 10, what is (3 - 7) mod 10?

A 6

B 4

C 0

D 7

3 - 7 = -4, add 10 to get 6, so (3 - 7) mod 10 = 6.

Why do programmers use modular arithmetic?

A To keep numbers within a fixed range

B To make numbers bigger

C To avoid using division

D To sort numbers

Modular arithmetic keeps numbers within a fixed range, useful for many programming tasks.

Explain modular arithmetic and how addition works in it.

Think about how a clock resets after 12 hours.

Describe how to handle subtraction in modular arithmetic when the first number is smaller.

Remember to keep the result between 0 and n-1.

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