Fast Exponentiation Power in Log N in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fast Exponentiation Function

What is the output of the following Go code that calculates 3 to the power 5 using fast exponentiation?

DSA Go

package main
import "fmt"
func fastPow(base, exp int) int {
    result := 1
    b := base
    e := exp
    for e > 0 {
        if e&1 == 1 {
            result *= b
        }
        b *= b
        e >>= 1
    }
    return result
}
func main() {
    fmt.Println(fastPow(3, 5))
}

A 125

B 15

C 243

D 81

💡 Hint

Remember that 3^5 means 3 multiplied by itself 5 times.

3^5 = 3 * 3 * 3 * 3 * 3 = 243. The fast exponentiation method efficiently calculates this by squaring and multiplying selectively.

🧠 Conceptual

intermediate

Number of Multiplications in Fast Exponentiation

For calculating base^exp using fast exponentiation, approximately how many multiplications are performed when exp = 1024?

A About 10 multiplications

B About 1024 multiplications

C About 512 multiplications

D About 2048 multiplications

💡 Hint

Think about how many times you can divide 1024 by 2 until you reach 1.

Fast exponentiation uses repeated squaring, reducing multiplications to roughly log2(exp). Since 2^10 = 1024, about 10 multiplications occur.

🔧 Debug

advanced

Identify the Runtime Error in Fast Exponentiation Code

What error will the following Go code produce when calculating 2^10?

DSA Go

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

A Runtime panic: integer divide by zero

B Syntax error: cannot assign to e%2

C Output: 1024

D Output: 512

💡 Hint

Check the condition inside the if statement carefully.

The code uses '=' instead of '==' in the if condition, causing a syntax error because '=' is assignment, not comparison.

❓ Predict Output

advanced

Output of Fast Exponentiation with Negative Exponent

What will be the output of this Go code that attempts to compute 2^-3 using fast exponentiation?

DSA Go

package main
import "fmt"
func fastPow(base, exp int) int {
    result := 1
    b := base
    e := exp
    for e > 0 {
        if e&1 == 1 {
            result *= b
        }
        b *= b
        e >>= 1
    }
    return result
}
func main() {
    fmt.Println(fastPow(2, -3))
}

A Runtime infinite loop

B 0

C Compilation error

D 1

💡 Hint

Consider how the loop condition handles negative exponents.

Since exp is negative, e > 0 is false initially, so the loop never runs and result remains 1.

🚀 Application

expert

Fast Exponentiation Modulo Large Prime

Which option correctly computes (5^117) mod 1000000007 using fast exponentiation in Go?

A

func modPow(base, exp, mod int) int {
    result := 1
    b := base % mod
    e := exp
    for e > 0 {
        if e&1 == 1 {
            result = (result * b) % mod
        }
        b = (b * b) % mod
        e >>= 1
    }
    return result
}

B

func modPow(base, exp, mod int) int {
    result := 1
    b := base % mod
    e := exp
    for e > 0 {
        if e&1 == 0 {
            result = (result * b) % mod
        }
        b = (b * b) % mod
        e >>= 1
    }
    return result
}

C

func modPow(base, exp, mod int) int {
    result := 0
    b := base % mod
    e := exp
    for e > 0 {
        if e&1 == 1 {
            result = (result + b) % mod
        }
        b = (b * b) % mod
        e >>= 1
    }
    return result
}

D

func modPow(base, exp, mod int) int {
    result := 1
    b := base
    e := exp
    for e > 0 {
        if e%2 == 1 {
            result = (result * b) % mod
        }
        b = (b * b) % mod
        e /= 2
    }
    return result
}

💡 Hint

Remember to initialize result as 1 and multiply only when the current bit is 1.

Option A correctly initializes result to 1, uses bitwise AND to check odd exponent bits, and applies modulo after each multiplication and squaring.

Practice

1. What is the main advantage of using fast exponentiation (power in log n) over the simple repeated multiplication method?

easy

A. It reduces the number of multiplications from n to log n

B. It uses less memory by storing all intermediate powers

C. It works only for even powers

D. It avoids multiplication completely

Solution

1. Step 1: Understand simple exponentiation

   Simple method multiplies the base by itself n times, so it takes n multiplications.

2. Step 2: Understand fast exponentiation

   Fast exponentiation uses repeated squaring, reducing multiplications to about log n times.

3. Final Answer:

   It reduces the number of multiplications from n to log n -> Option A

4. Quick Check:

   Fast exponentiation = fewer multiplications [OK]

Hint: Fast exponentiation cuts steps from n to log n [OK]

Common Mistakes:

• Thinking it only works for even powers
• Confusing memory use with speed
• Believing it avoids multiplication

2. Which of the following Go function signatures correctly represents a fast exponentiation function that calculates base^exp (integer power)?

easy

A. func fastPower(base float64, exp int) float64

B. func fastPower(base int, exp float64) int

C. func fastPower(base int, exp int) int

D. func fastPower(base int, exp int) float64

Solution

1. Step 1: Identify parameter types for integer power

   Base and exponent should be integers for integer power calculation.

2. Step 2: Check return type

   Return type should be int to match integer power result.

3. Final Answer:

   func fastPower(base int, exp int) int -> Option C

4. Quick Check:

   Integer base and exponent with int return [OK]

Hint: Use int for base, exponent, and return for integer powers [OK]

Common Mistakes:

• Using float64 for exponent when integer is needed
• Returning float64 instead of int
• Mixing base and exponent types

3. What is the output of the following Go code snippet?

func fastPower(base int, exp int) int {
    if exp == 0 {
        return 1
    }
    half := fastPower(base, exp/2)
    if exp%2 == 0 {
        return half * half
    } else {
        return half * half * base
    }
}

fmt.Println(fastPower(2, 5))

medium

A. 10

B. 32

C. 25

D. 16

Solution

1. Step 1: Trace recursive calls for fastPower(2, 5)

   fastPower(2,5) calls fastPower(2,2), which calls fastPower(2,1), which calls fastPower(2,0)=1.

2. Step 2: Calculate results bottom-up

   fastPower(2,1) = 1*1*2=2; fastPower(2,2) = 2*2=4; fastPower(2,5) = 4*4*2=32.

3. Final Answer:

   32 -> Option B

4. Quick Check:

   2^5 = 32 [OK]

Hint: Remember 2^5 = 32; fastPower uses recursion [OK]

Common Mistakes:

• Confusing multiplication order
• Forgetting to multiply by base for odd exponent
• Miscomputing base cases

4. The following Go code for fast exponentiation has a bug. What is the bug?

func fastPower(base int, exp int) int {
    if exp == 0 {
        return 0
    }
    half := fastPower(base, exp/2)
    if exp%2 == 0 {
        return half * half
    } else {
        return half * half * base
    }
}

medium

A. Function does not handle negative exponents

B. Missing multiplication by base for even exponents

C. Incorrect integer division for exp/2

D. Base case returns 0 instead of 1

Solution

1. Step 1: Check base case for exponent 0

   Exponent 0 means power is 1, but code returns 0, which is incorrect.

2. Step 2: Verify other parts

   Multiplication and division logic is correct; negative exponent handling is not required here.

3. Final Answer:

   Base case returns 0 instead of 1 -> Option D

4. Quick Check:

   Power of 0 exponent = 1 [OK]

Hint: Base case for exp=0 must return 1 [OK]

Common Mistakes:

• Returning 0 for exp=0 base case
• Ignoring negative exponent cases
• Misplacing multiplication logic

5. You want to compute (3^13) mod 7 efficiently using fast exponentiation in Go. Which modification is needed in the fastPower function to correctly compute this without overflow?

hard

A. Add modulo operation after each multiplication to keep numbers small

B. Use float64 type for base and exponent to handle large numbers

C. Multiply only once at the end after all recursion completes

D. Increase the base to base*mod to avoid overflow

Solution

1. Step 1: Understand modular exponentiation

   To avoid overflow and keep numbers small, apply modulo after each multiplication.

2. Step 2: Modify fastPower to include modulo

   Insert modulo operation after multiplying halves and base to keep intermediate results within mod.

3. Final Answer:

   Add modulo operation after each multiplication to keep numbers small -> Option A

4. Quick Check:

   Modulo after multiplication prevents overflow [OK]

Hint: Apply modulo after every multiplication step [OK]

Common Mistakes:

• Delaying modulo until end causes overflow
• Using float64 instead of int causes precision loss
• Multiplying base by mod increases value incorrectly