Why Modular Arithmetic Basics in DSA Go?

The Big Idea

Discover how a simple math trick can solve tricky problems with clocks and cycles effortlessly!

The Scenario

Imagine you are trying to keep track of hours on a clock. If you add 5 hours to 10 o'clock, you get 15, but clocks only show numbers from 1 to 12. Without a way to wrap around, you would get confusing results.

The Problem

Doing this wrapping manually means checking if numbers go beyond the limit and then subtracting the limit repeatedly. This is slow and easy to mess up, especially when numbers get very big or when doing many calculations.

The Solution

Modular arithmetic automatically wraps numbers around a fixed limit, like a clock. It makes calculations neat and error-free by always keeping results within a set range.

Before vs After

✗ Before

hours := 10
added := 5
result := hours + added
if result > 12 {
    result = result - 12
}

✓ After

hours := 10
added := 5
result := (hours + added) % 12
if result == 0 {
    result = 12
}

What It Enables

It enables easy handling of cycles, repeating patterns, and large number calculations without errors.

Real Life Example

Calculating the day of the week after adding many days, like finding what day it will be 100 days from today.

Key Takeaways

Manual wrapping is slow and error-prone.

Modular arithmetic keeps numbers within a fixed range automatically.

It is essential for cycles, clocks, and large number math.

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