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.