Fast Exponentiation Power in Log N in DSA C

Mental Model

We can find a number raised to a power quickly by breaking the problem into smaller parts using repeated squaring.

Analogy: Imagine folding a paper multiple times to reach a big thickness quickly instead of stacking sheets one by one.

power(n, e)
  e even -> power(n * n, e / 2)
  e odd  -> n * power(n * n, (e - 1) / 2)

Dry Run Walkthrough

Input: Calculate 3^13 using fast exponentiation

Goal: Compute 3 raised to the power 13 efficiently using repeated squaring

Step 1: Since 13 is odd, separate one 3 and reduce power to 12

result = 3 * power(3 * 3, 6)

Why: Odd powers are handled by taking one base out and making the exponent even

Step 2: Calculate power(9, 6) since 3*3=9 and 6 is even

power(9, 6) = power(9 * 9, 3) = power(81, 3)

Why: For even powers, square the base and halve the exponent

Step 3: Since 3 is odd, separate one 81 and reduce power to 2

power(81, 3) = 81 * power(81 * 81, 1) = 81 * power(6561, 1)

Why: Odd powers handled by separating one base and reducing exponent

Step 4: Calculate power(6561, 1) which is base itself

power(6561, 1) = 6561

Why: Power of 1 returns the base

Step 5: Multiply back all separated bases: 3 * 81 * 6561

result = 3 * 81 * 6561 = 1594323

Why: Combine all parts to get final power

Result:

1594323

Annotated Code

DSA C

#include <stdio.h>

// Function to compute n^e using fast exponentiation
long long fast_power(long long n, int e) {
    if (e == 0) return 1; // base case: any number^0 = 1
    if (e % 2 == 0) {
        // even exponent: square base and halve exponent
        long long half = fast_power(n * n, e / 2);
        return half;
    } else {
        // odd exponent: separate one base and reduce exponent
        return n * fast_power(n * n, (e - 1) / 2);
    }
}

int main() {
    long long base = 3;
    int exponent = 13;
    long long result = fast_power(base, exponent);
    printf("%lld\n", result);
    return 0;
}

if (e == 0) return 1; // base case: any number^0 = 1

stop recursion when exponent is zero

if (e % 2 == 0) {

check if exponent is even

long long half = fast_power(n * n, e / 2);

square base and halve exponent for even power

return half;

return result of recursive call for even exponent

return n * fast_power(n * n, (e - 1) / 2);

for odd exponent, multiply base once and recurse with squared base and halved exponent

Output

1594323

Complexity Analysis

Time: O(log e) because the exponent is halved at each recursive call

Space: O(log e) due to recursion call stack depth proportional to log of exponent

vs Alternative: Naive approach takes O(e) time by multiplying base e times, which is slower for large exponents

Edge Cases

exponent is zero

returns 1 immediately as any number to power 0 is 1

DSA C

if (e == 0) return 1;

exponent is one

returns base itself without further recursion

DSA C

return n * fast_power(n * n, (e - 1) / 2);

large exponent

efficiently computes power in logarithmic steps without overflow in recursion depth

DSA C

recursive calls halve exponent each time

When to Use This Pattern

When you need to compute large powers quickly, look for fast exponentiation using repeated squaring to reduce time from linear to logarithmic.

Common Mistakes

Mistake: Multiplying base e times instead of using repeated squaring
Fix: Use recursion or loop to square base and halve exponent to reduce steps

Mistake: Not handling odd exponents separately
Fix: Separate one base multiplication for odd exponents before recursion

Mistake: Forgetting base case when exponent is zero
Fix: Add condition to return 1 when exponent is zero

Summary

Computes power of a number efficiently using repeated squaring.

Use when you need to calculate large powers quickly without multiplying many times.

The key is to reduce the exponent by half each step by squaring the base.

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 time complexity from O(n) to O(log n)

B. It uses less memory than simple multiplication

C. It works only for positive exponents

D. It avoids using multiplication altogether

Solution

1. Step 1: Understand simple exponentiation time

   Simple repeated multiplication multiplies the base n times, so it takes O(n) time.

2. Step 2: Understand fast exponentiation time

   Fast exponentiation uses squaring and divides the problem size by 2 each step, so it takes O(log n) time.

3. Final Answer:

   It reduces the time complexity from O(n) to O(log n) -> Option A

4. Quick Check:

   Fast exponentiation = O(log n) [OK]

Hint: Remember: divide exponent by 2 each step for speed [OK]

Common Mistakes:

• Thinking it avoids multiplication
• Confusing time complexity with memory usage
• Assuming it only works for positive exponents

2. Which of the following is the correct C syntax to calculate pow(base, exponent) using fast exponentiation recursively?

easy

A. int fastPow(int base, int exp) { if (exp == 0) return 1; int half = fastPow(base, exp / 2); if (exp % 2 == 0) return half * half; else return base * half * half; }

B. int fastPow(int base, int exp) { int result = 1; for (int i = 0; i < exp; i++) result *= base; return result; }

C. int fastPow(int base, int exp) { if (exp == 1) return base; return base * fastPow(base, exp - 1); }

D. int fastPow(int base, int exp) { return base ^ exp; }

Solution

1. Step 1: Identify recursive fast exponentiation

   int fastPow(int base, int exp) { if (exp == 0) return 1; int half = fastPow(base, exp / 2); if (exp % 2 == 0) return half * half; else return base * half * half; } uses recursion, divides exponent by 2, and squares the half result, matching fast exponentiation logic.

2. Step 2: Check other options

   int fastPow(int base, int exp) { int result = 1; for (int i = 0; i < exp; i++) result *= base; return result; } is simple loop (not fast). int fastPow(int base, int exp) { if (exp == 1) return base; return base * fastPow(base, exp - 1); } is simple recursion without divide and conquer. int fastPow(int base, int exp) { return base ^ exp; } uses bitwise XOR, not power.

3. Final Answer:

   int fastPow(int base, int exp) { if (exp == 0) return 1; int half = fastPow(base, exp / 2); if (exp % 2 == 0) return half * half; else return base * half * half; } -> Option A

4. Quick Check:

   Recursive fast exponentiation = int fastPow(int base, int exp) { if (exp == 0) return 1; int half = fastPow(base, exp / 2); if (exp % 2 == 0) return half * half; else return base * half * half; } [OK]

Hint: Look for dividing exponent by 2 and squaring result [OK]

Common Mistakes:

• Using simple loops instead of divide and conquer
• Confusing bitwise XOR (^) with power
• Missing base case for exponent 0

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

int fastPow(int base, int exp) {
    if (exp == 0) return 1;
    int half = fastPow(base, exp / 2);
    if (exp % 2 == 0) return half * half;
    else return base * half * half;
}

int main() {
    printf("%d", fastPow(2, 5));
    return 0;
}

medium

A. 25

B. 32

C. 10

D. 16

Solution

1. Step 1: Trace fastPow(2, 5)

   fastPow(2,5) calls fastPow(2,2), which calls fastPow(2,1), which calls fastPow(2,0)=1. Then compute up: fastPow(2,1)=2*1*1=2, fastPow(2,2)=2*2=4, fastPow(2,5)=2*4*4=32.

2. Step 2: Confirm output

   The final printed value is 32.

3. Final Answer:

   32 -> Option B

4. Quick Check:

   2^5 = 32 [OK]

Hint: Calculate powers by halving exponent and squaring [OK]

Common Mistakes:

• Confusing multiplication order
• Forgetting base case returns 1
• Miscomputing odd exponent step

4. Identify the bug in the following fast exponentiation code and select the correct fix:

int fastPow(int base, int exp) {
    if (exp == 0) return 1;
    int half = fastPow(base, exp / 2);
    if (exp % 2 == 0) return half * half;
    else return base * half;
}

medium

A. Change exp / 2 to exp - 1;

B. Change base case to if (exp == 1) return base;

C. Change last line to return base * half * half;

D. No bug, code is correct

Solution

1. Step 1: Analyze odd exponent case

   For odd exponent, result should be base * half * half, but code returns base * half only, missing one multiplication.

2. Step 2: Fix the return statement

   Change last line to return base * half * half to correctly compute power for odd exponents.

3. Final Answer:

   Change last line to return base * half * half; -> Option C

4. Quick Check:

   Odd exponent step needs base * half * half [OK]

Hint: Remember odd exponent multiplies base once more [OK]

Common Mistakes:

• Returning base * half instead of base * half * half
• Changing base case incorrectly
• Replacing exp / 2 with exp - 1

5. You want to compute pow(base, exponent) modulo m efficiently using fast exponentiation. Which modification should you apply to the standard fast exponentiation algorithm to handle large numbers without overflow?

hard

A. Use floating point arithmetic instead of integers

B. Only apply modulo at the final return value

C. Increase the size of integer variables to long long

D. Apply modulo operation after each multiplication step

Solution

1. Step 1: Understand overflow risk

   Multiplying large numbers can overflow integer limits before modulo is applied.

2. Step 2: Apply modulo after each multiplication

   To avoid overflow and keep numbers small, apply modulo after every multiplication step in fast exponentiation.

3. Final Answer:

   Apply modulo operation after each multiplication step -> Option D

4. Quick Check:

   Modulo after each multiply prevents overflow [OK]

Hint: Modulo after every multiply keeps numbers small [OK]

Common Mistakes:

• Applying modulo only once at the end
• Using floating point causing precision errors
• Relying on bigger integer types without modulo