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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fast Exponentiation Function

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

DSA Python

def fast_power(base, exponent):
    result = 1
    while exponent > 0:
        if exponent % 2 == 1:
            result *= base
        base *= base
        exponent //= 2
    return result

print(fast_power(3, 5))

A 125

B null (infinite loop)

C 15

D 243

💡 Hint

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

The function uses fast exponentiation to compute 3^5 = 243 efficiently by squaring the base and reducing the exponent by half each iteration.

❓ Predict Output

intermediate

Result of Fast Power with Zero Exponent

What will be the output of this code when calculating 10 to the power 0 using fast exponentiation?

DSA Python

def fast_power(base, exponent):
    result = 1
    while exponent > 0:
        if exponent % 2 == 1:
            result *= base
        base *= base
        exponent //= 2
    return result

print(fast_power(10, 0))

A 10

B 1

C 0

D Error

💡 Hint

Any number to the power 0 is always?

By definition, any number raised to the power 0 is 1. The function returns 1 without entering the loop.

❓ Predict Output

advanced

Output of Fast Power with Negative Exponent

What will the following code output when calculating 2 to the power -3 using the given fast exponentiation function?

DSA Python

def fast_power(base, exponent):
    result = 1
    while exponent > 0:
        if exponent % 2 == 1:
            result *= base
        base *= base
        exponent //= 2
    return result

print(fast_power(2, -3))

A 1 (function does not handle negative exponents, returns 1)

B 1

C 2

D 0.125

💡 Hint

Check how the function handles negative exponents.

The function only works for non-negative exponents. Since exponent is negative, the while loop never runs and returns 1.

🧠 Conceptual

advanced

Time Complexity of Fast Exponentiation

What is the time complexity of the fast exponentiation algorithm that calculates base^exponent by repeatedly squaring the base and halving the exponent?

A O(n^2), where n is the exponent

B O(n), where n is the exponent

C O(log n), where n is the exponent

D O(1), constant time

💡 Hint

Think about how many times you can halve the exponent before it reaches zero.

Each iteration halves the exponent, so the number of steps is proportional to log base 2 of the exponent.

🔧 Debug

expert

Identify the Bug in Fast Exponentiation Code

The following code is intended to compute base^exponent using fast exponentiation. What is the bug that causes incorrect results for odd exponents?

DSA Python

def fast_power(base, exponent):
    result = 1
    while exponent > 0:
        if exponent % 2 == 1:
            result = base * base
        base = base * base
        exponent = exponent // 2
    return result

print(fast_power(2, 3))

A The result is overwritten instead of multiplied when exponent is odd

B The base is not squared correctly

C The exponent is not halved properly

D The initial result should be 0, not 1

💡 Hint

Check how the result variable is updated inside the loop.

The code assigns result = base * base instead of multiplying result by base when exponent is odd, causing wrong output.

Practice

1. What is the main advantage of using Fast Exponentiation to calculate a^b compared to the simple repeated multiplication?

easy

A. It works only for positive integers

B. It uses less memory than repeated multiplication

C. It reduces the time complexity from O(b) to O(log b)

D. It avoids using multiplication altogether

Solution

1. Step 1: Understand repeated multiplication complexity

   Calculating a^b by multiplying a by itself b times takes O(b) steps.

2. Step 2: Analyze fast exponentiation approach

   Fast exponentiation uses the idea of squaring and halving the exponent, reducing steps to O(log b).

3. Final Answer:

   It reduces the time complexity from O(b) to O(log b) -> Option C

4. Quick Check:

   Fast exponentiation = O(log b) [OK]

Hint: Remember: halve exponent each step for log speed [OK]

Common Mistakes:

• Thinking it avoids multiplication
• Confusing memory use with speed
• Assuming it only works for positive exponents

2. Which of the following is the correct base case for a recursive fast exponentiation function power(a, b) that calculates a^b?

easy

A. if b == 0: return 1

B. if a == 0: return 0

C. if b == 1: return 0

D. if a == 1: return b

Solution

1. Step 1: Recall mathematical rule for exponent zero

   Any number to the power 0 equals 1, so power(a, 0) should return 1.

2. Step 2: Check options for correct base case

   if b == 0: return 1 matches this rule: if b == 0: return 1.

3. Final Answer:

   if b == 0: return 1 -> Option A

4. Quick Check:

   Base case b=0 returns 1 [OK]

Hint: Base case: exponent zero returns 1 [OK]

Common Mistakes:

• Returning 0 when exponent is 1
• Confusing base and exponent in conditions
• Returning b instead of 1 for base case

3. What is the output of the following Python code?

def fast_power(a, b):
    if b == 0:
        return 1
    half = fast_power(a, b // 2)
    if b % 2 == 0:
        return half * half
    else:
        return half * half * a

print(fast_power(2, 5))

medium

A. 32

B. 10

C. 25

D. 16

Solution

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

   fast_power(2,5) calls fast_power(2,2), which calls fast_power(2,1), then fast_power(2,0) returns 1.

2. Step 2: Calculate values bottom-up

   fast_power(2,1) = 1*1*2 = 2
   fast_power(2,2) = 2*2 = 4
   fast_power(2,5) = 4*4*2 = 32

3. Final Answer:

   32 -> Option A

4. Quick Check:

   2^5 = 32 [OK]

Hint: Remember: odd exponent multiplies extra base [OK]

Common Mistakes:

• Confusing multiplication order
• Forgetting to multiply by base when exponent is odd
• Incorrect base case handling

4. The following code attempts to implement fast exponentiation but has a bug. What is the bug?

def fast_power(a, b):
    if b == 0:
        return 1
    half = fast_power(a, b // 2)
    if b % 2 == 1:
        return half * half
    else:
        return half * half * a

print(fast_power(3, 3))

medium

A. Function does not handle negative exponents

B. Base case should return 0 instead of 1

C. Multiplication order is incorrect

D. The condition for odd exponent is reversed

Solution

1. Step 1: Analyze the condition for odd exponent

   The code checks if b % 2 == 1 but returns half * half which is for even exponent.

2. Step 2: Identify correct logic for odd exponent

   For odd exponent, it should return half * half * a. The conditions are swapped.

3. Final Answer:

   The condition for odd exponent is reversed -> Option D

4. Quick Check:

   Odd exponent must multiply extra base [OK]

Hint: Odd exponent means multiply extra base factor [OK]

Common Mistakes:

• Swapping odd/even conditions
• Wrong base case return value
• Ignoring negative exponent cases

5. You want to compute 3^1000 mod 1000000007 efficiently using fast exponentiation. Which of the following modifications is necessary to the standard fast exponentiation algorithm to handle this?

hard

A. Convert exponent to binary string before calculation

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

C. Increase recursion depth limit to handle large exponent

D. Use floating point arithmetic to handle large numbers

Solution

1. Step 1: Understand the problem with large powers

   Calculating 3^1000 directly results in a huge number that can cause overflow or slow computation.

2. Step 2: Apply modulo at each multiplication step

   To keep numbers manageable and get correct modulo result, apply modulo after every multiplication.

3. Final Answer:

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

4. Quick Check:

   Modulo after multiplication keeps numbers small [OK]

Hint: Apply modulo after every multiplication step [OK]

Common Mistakes:

• Using floating point causing precision errors
• Not applying modulo inside recursion
• Trying to convert exponent to string unnecessarily