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

Recall & Review

beginner

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

It reduces the number of multiplications by using the property that x^n = (x^(n/2))^2 when n is even, and x^n = x * x^(n-1) when n is odd, allowing calculation in logarithmic time.

beginner

Why is Fast Exponentiation faster than the naive method?

Because it splits the exponent into halves repeatedly, reducing the problem size by half each time, resulting in O(log n) multiplications instead of O(n).

intermediate

In Fast Exponentiation, what happens when the exponent is odd?

We multiply the base once and then reduce the exponent by one to make it even, then continue with the halving process.

intermediate

Show the recursive formula used in Fast Exponentiation.

power(x, n) = 1 if n == 0; if n is even, power(x, n) = power(x, n/2) * power(x, n/2); if n is odd, power(x, n) = x * power(x, n-1).

beginner

What is the time complexity of Fast Exponentiation and why?

O(log n) because the exponent is divided by 2 at each step, reducing the problem size exponentially.

What is the time complexity of the Fast Exponentiation algorithm?

A O(1)

B O(n)

C O(n^2)

D O(log n)

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

In Fast Exponentiation, if the exponent n is even, what is the next step?

A Return 1 immediately

B Multiply x once and reduce n by 1

C Calculate power(x, n/2) and multiply it by itself

D Multiply x by power(x, n-1)

When n is even, we compute power(x, n/2) once and square it to get power(x, n).

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

A When n == 0, return 1

B When n == 1, return x

C When n is odd, return x

D When n is even, return x * x

The base case is when the exponent is zero, the result is 1 by definition.

If x = 2 and n = 5, what is the first step in Fast Exponentiation?

A Multiply 2 by power(2, 4)

B Calculate power(2, 2) and square it

C Return 1

D Multiply 2 by power(2, 5)

Since 5 is odd, multiply x once and reduce exponent by 1: 2 * power(2, 4).

Which of these is NOT a benefit of Fast Exponentiation?

A Uses less multiplication than naive method

B Always uses constant time

C Faster calculation for large exponents

D Reduces problem size by half each step

Fast Exponentiation is O(log n), not constant time.

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

Think about how splitting the exponent helps.

Describe the recursive steps of the Fast Exponentiation algorithm with an example for x=3 and n=6.

Walk through the calculation step by step.

Practice

1. What is the main advantage of using fast exponentiation (power) in log N time compared to the simple method of multiplying the base n times?

easy

A. It uses less memory by storing all intermediate powers

B. It reduces the number of multiplications from n to about log n

C. It works only for positive exponents

D. It avoids using multiplication altogether

Solution

1. Step 1: Understand simple exponentiation

   Simple method multiplies the base by itself n times, so it does n multiplications.

2. Step 2: Understand fast exponentiation advantage

   Fast exponentiation uses repeated squaring, reducing multiplications to about log n times.

3. Final Answer:

   It reduces the number of multiplications from n to about log n -> Option B

4. Quick Check:

   Fast exponentiation = fewer multiplications [OK]

Hint: Fast exponentiation halves exponent each step [OK]

Common Mistakes:

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

2. Which of the following Java method signatures correctly represents a fast exponentiation function that calculates base^exponent?

easy

A. int power(int base)

B. static void power(int base, int exponent)

C. public int power(int base, int exponent, int mod)

D. public static int power(int base, int exponent)

Solution

1. Step 1: Check method return type

   Power function returns an int result, so return type should be int.

2. Step 2: Check method parameters and modifiers

   Method should accept base and exponent as int, be static for utility use, and public for access.

3. Final Answer:

   public static int power(int base, int exponent) -> Option D

4. Quick Check:

   Correct signature = public static int power(int base, int exponent) [OK]

Hint: Power method returns int and takes base, exponent [OK]

Common Mistakes:

• Using void return type
• Missing static keyword
• Wrong number of parameters

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

public class Test {
  public static int power(int base, int exponent) {
    if (exponent == 0) return 1;
    int half = power(base, exponent / 2);
    if (exponent % 2 == 0) return half * half;
    else return half * half * base;
  }
  public static void main(String[] args) {
    System.out.println(power(2, 5));
  }
}

medium

A. 32

B. 25

C. 10

D. 16

Solution

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

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

2. Step 2: Calculate results bottom-up

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

3. Final Answer:

   32 -> Option A

4. Quick Check:

   2^5 = 32 [OK]

Hint: Remember 2^5 = 32, check recursion carefully [OK]

Common Mistakes:

• Confusing exponent division
• Forgetting to multiply base for odd exponent
• Incorrect base case handling

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

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

medium

A. Swap the if and else blocks to handle odd exponent correctly

B. Change exponent % 2 == 1 to exponent % 2 == 0

C. Add a base case for exponent == 1

D. Remove the recursive call and use a loop instead

Solution

1. Step 1: Analyze condition for odd exponent

   Current code returns half*half when exponent is odd, but it should multiply by base in that case.

2. Step 2: Fix condition blocks

   Swapping if and else blocks makes odd exponent return half*half*base and even exponent return half*half.

3. Final Answer:

   Swap the if and else blocks to handle odd exponent correctly -> Option A

4. Quick Check:

   Odd exponent multiplies extra base [OK]

Hint: Odd exponent needs extra base multiplication [OK]

Common Mistakes:

• Confusing odd/even condition
• Adding unnecessary base case
• Replacing recursion with loop without reason

5. You want to compute (3^1000) % 1000000007 efficiently using fast exponentiation. Which modification should you add to the standard fast exponentiation method to handle this correctly?

hard

A. Calculate 3^1000 first, then apply modulo once at the end

B. Use floating point arithmetic to handle large powers

C. Add modulo operation after every multiplication to keep numbers small

D. Use a loop instead of recursion to avoid stack overflow

Solution

1. Step 1: Understand modular exponentiation need

   Directly calculating 3^1000 is huge and causes overflow, so modulo must be applied during calculation.

2. Step 2: Apply modulo after each multiplication

   Adding modulo after each multiplication keeps intermediate results within integer limits and ensures correct final modulo result.

3. Final Answer:

   Add modulo operation after every multiplication to keep numbers small -> Option C

4. Quick Check:

   Modulo after multiplication prevents overflow [OK]

Hint: Apply modulo after every multiplication step [OK]

Common Mistakes:

• Applying modulo only once at the end
• Using floating point causing precision loss
• Ignoring overflow in recursion