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 and reusing results.

Analogy: Imagine climbing stairs two steps at a time instead of one. You reach the top faster by skipping steps smartly.

power(base, exponent)
  ↓
  base^exponent
  ↓
  base^(exponent/2) * base^(exponent/2) if exponent even
  or base * base^(exponent-1) if exponent odd

Dry Run Walkthrough

Input: Calculate 3^13 using fast exponentiation

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

Step 1: Check if exponent 13 is odd, multiply result by base 3 (result=3), square base to 9, halve exponent to 6

result = 3, base = 9, exponent = 6

Why: Odd exponent means we take one base out and handle the rest as even

Step 2: Square base: 9^2 = 81, halve exponent: 6 / 2 = 3 (even, no multiply)

base = 81, exponent = 3, result = 3

Why: We reduce exponent by half to speed up calculation

Step 3: Exponent 3 is odd, multiply result by base 81 (result=243), square base to 6561, halve exponent to 1

result = 243, base = 6561, exponent = 1

Why: Handle odd exponent by multiplying result

Step 4: Exponent 1 is odd, multiply result by base 6561 (result=1594323), halve exponent to 0

result = 1594323, exponent = 0

Why: Final multiplication for odd exponent

Result:

Final result = 1594323

Annotated Code

DSA C#

using System;

class FastExponentiation
{
    public static long Power(long baseNum, int exponent)
    {
        long result = 1;
        long currentBase = baseNum;
        int currentExponent = exponent;

        while (currentExponent > 0)
        {
            if ((currentExponent & 1) == 1) // odd exponent
                result *= currentBase; // multiply result by current base

            currentBase *= currentBase; // square the base
            currentExponent >>= 1; // halve the exponent
        }

        return result;
    }

    static void Main()
    {
        long baseNum = 3;
        int exponent = 13;
        long power = Power(baseNum, exponent);
        Console.WriteLine($"{baseNum}^{exponent} = {power}");
    }
}

if ((currentExponent & 1) == 1) // odd exponent

Check if exponent is odd to multiply result by current base

result *= currentBase; // multiply result by current base

Multiply accumulated result by base for odd exponent

currentBase *= currentBase; // square the base

Square the base to prepare for halving exponent

currentExponent >>= 1; // halve the exponent

Halve the exponent by shifting right

Output

3^13 = 1594323

Complexity Analysis

Time: O(log n) because the exponent is halved each step, reducing the number of multiplications

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Naive approach does n multiplications (O(n)), fast exponentiation reduces this to O(log n), making it much faster for large exponents

Edge Cases

Exponent is zero

Returns 1 because any number to power 0 is 1

DSA C#

while (currentExponent > 0)

Exponent is one

Returns base itself without extra multiplications

DSA C#

if ((currentExponent & 1) == 1)

Base is zero and exponent positive

Returns 0 as zero to any positive power is zero

DSA C#

result *= currentBase

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 result by base every time without checking if exponent is odd
Fix: Only multiply result by base when exponent is odd

Mistake: Not halving the exponent correctly, causing infinite loops
Fix: Use right shift or divide exponent by 2 each iteration

Summary

Computes base raised to exponent efficiently using repeated squaring.

Use when you need fast power calculation especially for large exponents.

The key is to halve the exponent each step and square the base, multiplying result only when exponent is odd.

Practice

1. What is the main advantage of using Fast Exponentiation Power in Log N over the simple repeated multiplication method?

easy

A. It works only for positive exponents

B. It uses less memory by storing all intermediate powers

C. It reduces the time complexity from linear to logarithmic

D. It avoids multiplication altogether

Solution

1. Step 1: Understand the time complexity of simple exponentiation

   Simple repeated multiplication multiplies the base by itself n times, which takes O(n) time.

2. Step 2: Understand the time complexity of fast exponentiation

   Fast exponentiation uses squaring and reduces the number of multiplications to about O(log n).

3. Final Answer:

   It reduces the time complexity from linear to logarithmic -> Option C

4. Quick Check:

   Fast exponentiation = O(log n) time [OK]

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

Common Mistakes:

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

2. Which of the following C# code snippets correctly implements the fast exponentiation method to compute pow(base, exponent)?

easy

A. int FastPow(int baseVal, int exp) { int result = 1; while (exp > 0) { if ((exp & 1) == 1) result *= baseVal; baseVal *= baseVal; exp >>= 1; } return result; }

B. int FastPow(int baseVal, int exp) { int result = 0; for (int i = 0; i < exp; i++) result += baseVal; return result; }

C. int FastPow(int baseVal, int exp) { if (exp == 0) return 0; return baseVal * FastPow(baseVal, exp - 1); }

D. int FastPow(int baseVal, int exp) { int result = 1; for (int i = 0; i < exp; i++) result *= baseVal; return result; }

Solution

1. Step 1: Analyze the code for fast exponentiation logic

   int FastPow(int baseVal, int exp) { int result = 1; while (exp > 0) { if ((exp & 1) == 1) result *= baseVal; baseVal *= baseVal; exp >>= 1; } return result; } uses bitwise operations to check odd exponent and squares base, which is the fast exponentiation method.

2. Step 2: Check other options for correctness

   int FastPow(int baseVal, int exp) { int result = 0; for (int i = 0; i < exp; i++) result += baseVal; return result; } adds baseVal repeatedly (wrong for power), C returns 0 for exp=0 (should be 1), D uses simple loop (not fast).

3. Final Answer:

   int FastPow(int baseVal, int exp) { int result = 1; while (exp > 0) { if ((exp & 1) == 1) result *= baseVal; baseVal *= baseVal; exp >>= 1; } return result; } -> Option A

4. Quick Check:

   Bitwise & squaring = fast exponentiation [OK]

Hint: Look for bitwise checks and squaring in code [OK]

Common Mistakes:

• Using addition instead of multiplication
• Returning 0 for exponent 0
• Using simple loops instead of bitwise

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

int FastPow(int baseVal, int exp) {
    int result = 1;
    while (exp > 0) {
        if ((exp & 1) == 1) result *= baseVal;
        baseVal *= baseVal;
        exp >>= 1;
    }
    return result;
}

Console.WriteLine(FastPow(3, 4));

medium

A. 81

B. 64

C. 27

D. 12

Solution

1. Step 1: Trace the fast exponentiation for base=3, exp=4

   exp=4 (100b): - exp even, skip multiply, base=3*3=9, exp=2 - exp=2 (10b): even, skip multiply, base=9*9=81, exp=1 - exp=1 (1b): odd, multiply result=1*81=81, base=81*81=6561, exp=0 Loop ends.

2. Step 2: Final result is 81

   The function returns 81, which is 3^4.

3. Final Answer:

   81 -> Option A

4. Quick Check:

   3^4 = 81 [OK]

Hint: Remember to square base and halve exponent each step [OK]

Common Mistakes:

• Multiplying when exponent bit is zero
• Not updating base correctly
• Confusing exponent bits

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

int FastPow(int baseVal, int exp) {
    int result = 1;
    while (exp > 0) {
        if ((exp & 1) == 1) result *= baseVal;
        baseVal *= baseVal;
        exp = exp / 2;
    }
    return result;
}

medium

A. Replace exp = exp / 2; with exp >>= 1; for efficiency

B. Change multiplication to addition in result *= baseVal;

C. Initialize result to 0 instead of 1

D. Add a check for negative exponent at start

Solution

1. Step 1: Analyze the code for handling negative exponents

   The code does not handle negative exponents, since while (exp > 0) skips the loop and returns 1, which is wrong.

2. Step 2: Identify the fix

   Adding a check for negative exponent and handling it (e.g., returning 0 or using reciprocal) is necessary.

3. Final Answer:

   Add a check for negative exponent at start -> Option D

4. Quick Check:

   Negative exponent needs special handling [OK]

Hint: Always check for negative exponents before loop [OK]

Common Mistakes:

• Ignoring negative exponents
• Changing result initialization incorrectly
• Replacing division with bit shift without understanding

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

hard

A. Use floating point arithmetic instead of integers

B. Apply modulo m after every multiplication step

C. Only apply modulo m at the end of the computation

D. Increase the size of integer variables to long long

Solution

1. Step 1: Understand overflow risk in large exponentiation

   Multiplying large numbers repeatedly can cause integer overflow before final modulo.

2. Step 2: Apply modulo at each multiplication

   Taking modulo after every multiplication keeps intermediate results small and prevents overflow.

3. Final Answer:

   Apply modulo m after every multiplication step -> Option B

4. Quick Check:

   Modulo after each multiply avoids overflow [OK]

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

Common Mistakes:

• Applying modulo only once at end
• Using floating point causing precision loss
• Ignoring overflow risk