Modular Arithmetic Basics in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Modular Addition

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

DSA Go

package main
import "fmt"
func main() {
	const mod = 7
	a := 5
	b := 6
	result := (a + b) % mod
	fmt.Println(result)
}

A 1

B 4

C 0

D 11

💡 Hint

Remember modular addition means adding then taking remainder with mod.

5 + 6 = 11, 11 % 7 = 4, so output is 4.

❓ Predict Output

intermediate

Modular Multiplication Result

What does this Go code print after modular multiplication?

DSA Go

package main
import "fmt"
func main() {
	const mod = 10
	a := 4
	b := 3
	result := (a * b) % mod
	fmt.Println(result)
}

A 2

B 12

C 7

D 1

💡 Hint

Multiply first, then take remainder with mod.

4 * 3 = 12, 12 % 10 = 2, so output is 2.

🧠 Conceptual

advanced

Modular Inverse Existence

Which condition must be true for a modular inverse of a number 'a' modulo 'm' to exist?

A 'm' is a prime number

B 'a' is less than 'm'

C 'a' and 'm' are coprime (greatest common divisor is 1)

D 'a' is even

💡 Hint

Think about when division modulo is possible.

A modular inverse exists only if 'a' and 'm' share no common divisors other than 1.

❓ Predict Output

advanced

Output of Modular Exponentiation

What is the output of this Go code performing modular exponentiation?

DSA Go

package main
import "fmt"
func modExp(base, exp, mod int) int {
	result := 1
	b := base % mod
	e := exp
	for e > 0 {
		if e%2 == 1 {
			result = (result * b) % mod
		}
		b = (b * b) % mod
		e /= 2
	}
	return result
}
func main() {
	fmt.Println(modExp(3, 4, 5))
}

A 1

B 4

C 3

D 2

💡 Hint

Calculate 3^4 mod 5 step by step.

3^4 = 81, 81 % 5 = 1, but careful with code steps.

🧠 Conceptual

expert

Why Use Modular Arithmetic in Algorithms?

Why do many algorithms use modular arithmetic when working with large numbers?

A To make numbers negative

B To sort numbers faster

C To increase the size of numbers exponentially

D To keep numbers within a fixed range and avoid overflow

💡 Hint

Think about computer memory limits and number size.

Modular arithmetic keeps numbers small and manageable, preventing overflow.

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