Fast Exponentiation Power in Log N in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind Fast Exponentiation (Power) algorithm?

It reduces the number of multiplications by repeatedly squaring the base and using the binary representation of the exponent, achieving O(log n) time instead of O(n).

beginner

In Fast Exponentiation, what do you do when the current exponent bit is 1?

Multiply the result by the current base value before squaring the base for the next bit.

intermediate

Why does Fast Exponentiation run in O(log n) time?

Because it halves the exponent at each step by shifting bits, so the number of steps equals the number of bits in the exponent, which is about log2(n).

intermediate

Show the step-by-step calculation of 3^13 using Fast Exponentiation.

13 in binary is 1101. Steps: result=1, base=3 Bit 1 (LSB): multiply result by base → result=3 Square base → base=9 Bit 0: no multiply Square base → base=81 Bit 1: multiply result by base → result=3*81=243 Square base → base=6561 Bit 1: multiply result by base → result=243*6561=1594323 Final result=1594323

beginner

What is the base case for the Fast Exponentiation recursive approach?

When the exponent is 0, return 1 because any number to the power 0 is 1.

What is the time complexity of Fast Exponentiation for calculating x^n?

A O(1)

B O(n)

C O(n log n)

D O(log n)

Fast Exponentiation reduces the exponent by half each step, so it runs in O(log n) time.

In Fast Exponentiation, if the current exponent bit is 0, what should you do?

A Add base to result

B Multiply result by base

C Square the base only

D Stop the algorithm

When the bit is 0, you only square the base and do not multiply the result.

Which of these is NOT a benefit of Fast Exponentiation?

A Always uses recursion

B Uses less memory than naive method

C Works well with modular arithmetic

D Faster calculation for large exponents

Fast Exponentiation can be implemented iteratively or recursively; recursion is not mandatory.

What is the result of 2^5 using Fast Exponentiation?

A 32

B 10

C 25

D 64

2^5 = 32.

Which operation is repeated in Fast Exponentiation to reduce the exponent?

A Adding 1

B Dividing exponent by 2

C Multiplying exponent by 2

D Subtracting 1

The exponent is divided by 2 (shifted right) each step to reduce the problem size.

Explain how Fast Exponentiation reduces the number of multiplications compared to the naive method.

Think about how the exponent is broken down in powers of two.

Describe the iterative steps to compute 5^11 using Fast Exponentiation.

Walk through each bit of the exponent from least significant to most.

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