Modular Arithmetic Basics in DSA Go - Time & Space Complexity

Time Complexity: Modular Arithmetic Basics

O(log n)

Understanding Time Complexity

We want to understand how the time needed to do modular arithmetic operations changes as numbers get bigger.

Specifically, how does the cost grow when we do repeated modular calculations?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

package main

func modAdd(a, b, m int) int {
    return (a + b) % m
}

func modMul(a, b, m int) int {
    return (a * b) % m
}

func modExp(base, exp, m int) int {
    result := 1
    for exp > 0 {
        if exp%2 == 1 {
            result = (result * base) % m
        }
        base = (base * base) % m
        exp = exp / 2
    }
    return result
}

This code shows modular addition, multiplication, and fast modular exponentiation using repeated squaring.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The loop inside modExp repeats while halving the exponent.
• How many times: The loop runs about log_2(exp) times because the exponent is divided by 2 each step.

How Execution Grows With Input

As the exponent grows, the number of loop steps grows slowly because we halve the exponent each time.

Input Size (exp)	Approx. Operations
10	About 4 steps
100	About 7 steps
1000	About 10 steps

Pattern observation: Doubling the exponent adds only one more step, so growth is very slow.

Final Time Complexity

Time Complexity: O(log n)

This means the time to compute modular exponentiation grows slowly as the exponent gets bigger, making it efficient for large numbers.

Common Mistake

[X] Wrong: "Modular exponentiation takes as long as the exponent value because it loops that many times."

[OK] Correct: The loop actually halves the exponent each time, so it runs much fewer times than the exponent's value.

Interview Connect

Understanding modular arithmetic time complexity helps you solve problems with large numbers efficiently, a common skill interviewers look for.

Self-Check

"What if we changed the modular exponentiation to use simple repeated multiplication without halving the exponent? How would the time complexity change?"

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