Modular Arithmetic Basics in DSA Go - Build from Scratch

Modular Arithmetic Basics

📖 Scenario: You are working on a simple calculator that deals with modular arithmetic. Modular arithmetic is like a clock where numbers wrap around after reaching a certain value called the modulus.For example, if the modulus is 5, then after 4 comes 0 again (like hours on a clock).

🎯 Goal: Build a small Go program that calculates the modular sum of a list of numbers using a given modulus.This will help you understand how to use the modulus operator (%) in Go.

📋 What You'll Learn

Create a slice of integers with exact values

Create a variable for the modulus value

Calculate the sum of all numbers modulo the modulus

Print the final modular sum

💡 Why This Matters

🌍 Real World

Modular arithmetic is used in computer science for hashing, cryptography, and cyclic data structures like clocks.

💼 Career

Understanding modular arithmetic helps in coding interviews and working with algorithms that require wrap-around calculations.

1

Create the list of numbers

Create a slice of integers called numbers with these exact values: 7, 12, 5, 20, 3.

DSA Go

package main

func main() {
    // Create the slice numbers with values 7, 12, 5, 20, 3
    // Your code here
}

Hint

Use numbers := []int{7, 12, 5, 20, 3} to create the slice.

2

Set the modulus value

Create an integer variable called modulus and set it to 10.

DSA Go

package main

func main() {
    numbers := []int{7, 12, 5, 20, 3}
    // Create the modulus variable and set it to 10
    // Your code here
}

Hint

Use modulus := 10 to create the modulus variable.

3

Calculate the modular sum

Create an integer variable called modSum and set it to 0. Then use a for loop with variable num to iterate over numbers. Inside the loop, add num to modSum and then update modSum to modSum % modulus.

DSA Go

package main

func main() {
    numbers := []int{7, 12, 5, 20, 3}
    modulus := 10
    // Calculate modular sum
    // Your code here
}

Hint

Initialize modSum to 0. Use for _, num := range numbers to loop. Update modSum inside the loop.

4

Print the modular sum

Use fmt.Println(modSum) to print the final modular sum. Remember to import "fmt" at the top.

DSA Go

package main

import "fmt"

func main() {
    numbers := []int{7, 12, 5, 20, 3}
    modulus := 10
    modSum := 0
    for _, num := range numbers {
        modSum += num
        modSum %= modulus
    }
    // Print the modular sum
    // Your code here
}

Hint

Use fmt.Println(modSum) to show the result. The output should be 7.

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