Why Fast Exponentiation Power in Log N in DSA C++?

The Big Idea

Discover how to power up calculations without waiting forever!

The Scenario

Imagine you want to calculate a large power like 2³⁰ by multiplying 2 by itself 30 times manually.

Doing this step-by-step takes a long time and is tiring.

The Problem

Multiplying the base repeatedly for every power is slow and wastes time.

It also increases the chance of mistakes if done by hand or in code without optimization.

The Solution

Fast exponentiation uses a smart way to reduce the number of multiplications by splitting the power in halves.

This method calculates powers quickly in about log₂(n) steps instead of n steps.

Before vs After

✗ Before

int power(int base, int exponent) {
    int result = 1;
    for (int i = 0; i < exponent; i++) {
        result *= base;
    }
    return result;
}

✓ After

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

What It Enables

This technique enables you to compute very large powers efficiently, making algorithms faster and more practical.

Real Life Example

Fast exponentiation is used in cryptography to quickly calculate keys and encrypt data securely.

Key Takeaways

Manual repeated multiplication is slow for large powers.

Fast exponentiation reduces steps using divide and conquer.

It improves performance from linear to logarithmic time.

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