Fast Exponentiation Power in Log N in DSA Java

Mental Model

We can find a number raised to a power quickly by breaking the problem into smaller parts using repeated squaring.

Analogy: Imagine you want to climb 8 steps quickly. Instead of taking one step at a time, you jump 4 steps twice. Similarly, we square the number and reduce the power by half each time.

base = 2
power = 8

2^8 = ?

Visual:
2 -> 2^2 -> 2^4 -> 2^8
 ↑     ↑      ↑
start square square square

Dry Run Walkthrough

Input: base = 2, power = 10

Goal: Calculate 2 raised to the power 10 quickly using repeated squaring

Step 1: power is even, square base and halve power

base = 4, power = 5

Why: When power is even, we can square the base and reduce power by half to speed up calculation

Step 2: power is odd, multiply result by base and reduce power by 1

result = 4, base = 16, power = 2

Why: For odd power, multiply result by base once and make power even

Step 3: power is even, square base and halve power

base = 256, power = 1

Why: Square base and halve power again to reduce steps

Step 4: power is odd, multiply result by base and reduce power by 1

result = 1024, power = 0

Why: Multiply final result by base when power is odd and finish

Result:

result = 1024

Annotated Code

DSA Java

public class FastExponentiation {
    public static long power(long base, long exponent) {
        long result = 1;
        long currBase = base;
        long currExp = exponent;

        while (currExp > 0) {
            if ((currExp & 1) == 1) {
                result *= currBase; // multiply result by base when exponent bit is 1
            }
            currBase *= currBase; // square the base
            currExp >>= 1; // halve the exponent
        }
        return result;
    }

    public static void main(String[] args) {
        long base = 2;
        long exponent = 10;
        long answer = power(base, exponent);
        System.out.println(base + "^" + exponent + " = " + answer);
    }
}

if ((currExp & 1) == 1) {

check if current exponent bit is odd to multiply result by base

result *= currBase; // multiply result by base when exponent bit is 1

multiply accumulated result by current base for odd exponent

currBase *= currBase; // square the base

square the base to prepare for next bit

currExp >>= 1; // halve the exponent

shift exponent right to process next bit

Output

2^10 = 1024

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 takes O(n) multiplications by multiplying base exponent times, which is slower for large exponents

Edge Cases

exponent = 0

returns 1 because any number to power 0 is 1

DSA Java

while (currExp > 0) {

base = 0 and exponent > 0

returns 0 because 0 raised to any positive power is 0

DSA Java

result *= currBase;

exponent = 1

returns base itself without extra squaring

DSA Java

if ((currExp & 1) == 1) {

When to Use This Pattern

When you need to calculate large powers quickly, look for the fast exponentiation pattern using repeated squaring to reduce time from linear to logarithmic.

Common Mistakes

Mistake: Multiplying the result by base every time without checking if exponent bit is odd
Fix: Only multiply result by base when the current exponent bit is 1 (odd)

Mistake: Not squaring the base each iteration
Fix: Square the base after processing each bit to prepare for the next

Mistake: Not halving the exponent properly
Fix: Use right shift or divide exponent by 2 each iteration

Summary

Calculates base raised to exponent quickly using repeated squaring.

Use when you need to compute large powers efficiently.

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

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