Fast Exponentiation Power in Log N in DSA Java - Build from Scratch

Fast Exponentiation Power in Log N

📖 Scenario: Imagine you are building a calculator app that needs to quickly find the power of a number. Instead of multiplying the number many times, you want to use a faster way to get the result.

🎯 Goal: Build a Java program that calculates base raised to the power exponent using fast exponentiation, which works in logarithmic time.

📋 What You'll Learn

Create two integer variables base and exponent with given values

Create a variable result to store the final power value

Use a while loop to implement fast exponentiation logic

Print the final result after calculation

💡 Why This Matters

🌍 Real World

Fast exponentiation is used in computer graphics, cryptography, and scientific calculations where quick power calculations are needed.

💼 Career

Understanding fast exponentiation helps in optimizing algorithms and is a common topic in coding interviews and software development.

1

Create base and exponent variables

Create two integer variables called base and exponent with values 3 and 5 respectively.

DSA Java

// Your code here

Hint

Use int base = 3; and int exponent = 5; to create the variables.

2

Initialize result variable

Create an integer variable called result and set it to 1. This will hold the final power value.

DSA Java

int base = 3;
int exponent = 5;
// Your code here

Hint

Set result to 1 because multiplying by 1 does not change the value.

3

Implement fast exponentiation loop

Use a while loop with the condition exponent > 0. Inside the loop, if exponent % 2 == 1, multiply result by base. Then square base by multiplying it by itself. Finally, divide exponent by 2 using integer division.

DSA Java

int base = 3;
int exponent = 5;
int result = 1;
// Your code here

Hint

Remember to check if the exponent is odd using exponent % 2 == 1 and update result accordingly.

4

Print the final result

Print the value of result using System.out.println(result);.

DSA Java

int base = 3;
int exponent = 5;
int result = 1;

while (exponent > 0) {
    if (exponent % 2 == 1) {
        result *= base;
    }
    base *= base;
    exponent /= 2;
}
// Your code here

Hint

The output should be the value of 3 to the power 5, which is 243.

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