Fast Exponentiation Power in Log N in DSA C++

Mental Model

To find a number raised to a power quickly by breaking the problem into smaller parts and reusing results.

Analogy: Like folding a paper multiple times: instead of folding one by one, you fold it in halves to reach the goal faster.

power(n, e)
  ↓
Divide e by 2 -> power(n, e/2) -> reuse result -> combine

Example:
  2^8
  ↓
  2^4 * 2^4
  ↓
  (2^2 * 2^2) * (2^2 * 2^2)
  ↓
  ...

Dry Run Walkthrough

Input: Calculate 2^10 using fast exponentiation

Goal: Compute 2 raised to the power 10 efficiently using repeated squaring

Step 1: Check if exponent 10 is even, split into 2^(10/2) * 2^(10/2)

2^10 = 2^5 * 2^5

Why: Splitting exponent reduces the problem size by half

Step 2: Calculate 2^5 by splitting into 2^(5//2) * 2^(5//2) * 2 (because 5 is odd)

2^5 = 2^2 * 2^2 * 2

Why: Odd exponent handled by multiplying an extra base

Step 3: Calculate 2^2 by splitting into 2^(2/2) * 2^(2/2)

2^2 = 2^1 * 2^1

Why: Keep splitting until exponent is 1

Step 4: Calculate 2^1 which is base case, return 2

2^1 = 2

Why: Base case stops recursion

Step 5: Combine results: 2^2 = 2 * 2 = 4

2^2 = 4

Why: Multiply halves to get full power

Step 6: Combine results: 2^5 = 4 * 4 * 2 = 32

2^5 = 32

Why: Multiply halves and extra base for odd exponent

Step 7: Combine results: 2^10 = 32 * 32 = 1024

2^10 = 1024

Why: Final multiplication of halves

Result:

2^10 = 1024

Annotated Code

DSA C++

#include <iostream>
using namespace std;

// Function to compute n^e using fast exponentiation
long long fastPower(long long n, long long e) {
    if (e == 0) return 1; // base case: n^0 = 1
    long long half = fastPower(n, e / 2); // compute n^(e/2) recursively
    if (e % 2 == 0) {
        return half * half; // if even exponent, multiply halves
    } else {
        return half * half * n; // if odd exponent, multiply halves and base once more
    }
}

int main() {
    long long base = 2;
    long long exponent = 10;
    long long result = fastPower(base, exponent);
    cout << base << "^" << exponent << " = " << result << endl;
    return 0;
}

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

stop recursion when exponent is zero

long long half = fastPower(n, e / 2); // compute n^(e/2) recursively

reduce problem size by half

if (e % 2 == 0) { return half * half; }

combine halves for even exponent

else { return half * half * n; }

combine halves and multiply base for odd exponent

Output

2^10 = 1024

Complexity Analysis

Time: O(log n) because the exponent is divided by 2 at each recursive call

Space: O(log n) due to recursion call stack depth proportional to log n

vs Alternative: Naive approach is O(n) by multiplying base n 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; // base case: n^0 = 1

Exponent is one

Returns base itself after recursion ends

DSA C++

Handled implicitly by recursion and multiplication

Large exponent

Efficiently computes power without timeout due to logarithmic steps

DSA C++

long long half = fastPower(n, e / 2);

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 n times directly causing slow performance
Fix: Use recursive halving of exponent and multiply halves instead

Mistake: Not handling odd exponents correctly by missing extra multiplication
Fix: Multiply by base once more when exponent is odd

Mistake: Forgetting base case for exponent zero leading to infinite recursion
Fix: Add base case: if exponent is zero, return 1

Summary

Computes power of a number efficiently by splitting exponent in half repeatedly.

Use when you need to calculate large powers quickly without slow repeated multiplication.

The key is to reuse results of smaller powers and multiply them to get the full power.

Practice

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

easy

A. It works only for positive exponents

B. It reduces the time complexity from O(n) to O(log n)

C. It uses less memory by storing intermediate results

D. It avoids using multiplication altogether

Solution

1. Step 1: Understand simple exponentiation time

   Simple repeated multiplication takes n multiplications for power n, so O(n) time.

2. Step 2: Analyze fast exponentiation time

   Fast exponentiation splits power by half each step, reducing steps to about log n, so O(log n) time.

3. Final Answer:

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

4. Quick Check:

   Fast exponentiation = O(log n) [OK]

Hint: Fast exponentiation halves power each step [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 base case for a recursive fast exponentiation function computing x^n?

easy

A. if (x == 0) return 0;

B. if (x == 1) return n;

C. if (n == 1) return 0;

D. if (n == 0) return 1;

Solution

1. Step 1: Identify base case for exponent zero

   Any number to the power 0 is 1, so if n == 0, return 1.

2. Step 2: Check other options

   Other options do not correctly represent the base case for power calculation.

3. Final Answer:

   if (n == 0) return 1; -> Option D

4. Quick Check:

   Base case n=0 returns 1 [OK]

Hint: Power zero always returns 1 [OK]

Common Mistakes:

• Returning 0 for n=1
• Confusing base case with input x values
• Returning n instead of 1 for base case

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

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

int main() {
    std::cout << fastPow(2, 5);
    return 0;
}

medium

A. 32

B. 16

C. 25

D. 10

Solution

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

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

2. Step 2: Calculate values bottom-up

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

3. Final Answer:

   32 -> Option A

4. Quick Check:

   2^5 = 32 [OK]

Hint: Remember odd powers multiply extra x once [OK]

Common Mistakes:

• Calculating 2^5 as 16 by missing odd case
• Confusing multiplication order
• Forgetting base case returns 1

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

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

medium

A. Multiplying by n instead of x in the odd case

B. Missing base case for n == 1

C. Using integer division incorrectly

D. Not handling negative powers

Solution

1. Step 1: Check odd power multiplication

   In the odd case, code multiplies by n instead of x, which is incorrect.

2. Step 2: Confirm correct multiplication

   It should multiply by x to account for the extra factor in odd powers.

3. Final Answer:

   Multiplying by n instead of x in the odd case -> Option A

4. Quick Check:

   Odd power multiply by x, not n [OK]

Hint: Multiply by base x, not exponent n, for odd powers [OK]

Common Mistakes:

• Confusing n and x in multiplication
• Thinking base case missing causes this bug
• Ignoring negative power handling

5. You want to compute (3^13) % 7 efficiently using fast exponentiation with modulo. Which of the following code snippets correctly implements this?

hard

A. int modPow(int x, int n, int m) {
if (n == 0) return 1;
int half = modPow(x, n / 2, m);
int halfSq = (half * half) % m;
if (n % 2 == 0) return (halfSq * x) % m;
else return halfSq;
}

B. int modPow(int x, int n, int m) {
if (n == 0) return 0;
int half = modPow(x, n / 2, m);
int halfSq = (half + half) % m;
if (n % 2 == 0) return halfSq;
else return (halfSq * x) % m;
}

C. int modPow(int x, int n, int m) {
if (n == 0) return 1;
int half = modPow(x, n / 2, m);
int halfSq = (half * half) % m;
if (n % 2 == 1) return (halfSq * x) % m;
else return halfSq;
}

D. int modPow(int x, int n, int m) {
if (n == 1) return x % m;
int half = modPow(x, n / 2, m);
int halfSq = (half * half) % m;
if (n % 2 == 1) return halfSq;
else return (halfSq * x) % m;
}

Solution

1. Step 1: Check base case and modulo usage

   Base case returns 1 for n=0, correct. Multiplications use modulo to avoid overflow.

2. Step 2: Verify odd and even power handling

   For odd n, multiply halfSq by x modulo m; for even n, return halfSq. int modPow(int x, int n, int m) { if (n == 0) return 1; int half = modPow(x, n / 2, m); int halfSq = (half * half) % m; if (n % 2 == 1) return (halfSq * x) % m; else return halfSq; } matches this logic correctly.

3. Final Answer:

   code correctly implements fast exponentiation with modulo -> Option C

4. Quick Check:

   Modulo applied after each multiplication [OK]

Hint: Apply modulo after every multiplication step [OK]

Common Mistakes:

• Returning 0 for base case
• Using addition instead of multiplication
• Swapping odd and even cases