Fast Exponentiation Power in Log N in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of fast exponentiation with positive exponent

What is the output of the following Java code that calculates 3 to the power 5 using fast exponentiation?

DSA Java

public class Power {
    public static long fastPow(long base, long exp) {
        long result = 1;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result *= base;
            }
            base *= base;
            exp >>= 1;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(fastPow(3, 5));
    }
}

A 243

B 81

C 15

D 125

💡 Hint

Recall that 3^5 means 3 multiplied by itself 5 times.

3^5 = 3 * 3 * 3 * 3 * 3 = 243. The fast exponentiation method efficiently calculates this by squaring and multiplying selectively.

❓ Predict Output

intermediate

Output when exponent is zero

What will be printed by this Java code when calculating 10 to the power 0 using fast exponentiation?

DSA Java

public class PowerZero {
    public static long fastPow(long base, long exp) {
        long result = 1;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result *= base;
            }
            base *= base;
            exp >>= 1;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(fastPow(10, 0));
    }
}

A 1

B 0

C 10

D Exception thrown

💡 Hint

Any number raised to the power 0 is 1.

By definition, any non-zero number to the power 0 equals 1. The code returns 1 immediately since the loop does not run.

❓ Predict Output

advanced

Output of fast exponentiation with negative exponent (incorrect handling)

What will be the output of this Java code when calculating 2 to the power -3 using the given fast exponentiation method?

DSA Java

public class PowerNegative {
    public static long fastPow(long base, long exp) {
        long result = 1;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result *= base;
            }
            base *= base;
            exp >>= 1;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(fastPow(2, -3));
    }
}

A Exception thrown

B 1

C 0

D -8

💡 Hint

Check how the while loop condition handles negative exponents.

Since exp is negative, the condition exp > 0 is false initially, so the loop never runs and result remains 1.

🧠 Conceptual

advanced

Time complexity of fast exponentiation

What is the time complexity of the fast exponentiation algorithm that uses repeated squaring and bitwise operations to compute base^exp?

A O(1), constant time

B O(n), where n is the exponent

C O(n^2), where n is the exponent

D O(log n), where n is the exponent

💡 Hint

Consider how many times the exponent can be divided by 2.

The algorithm reduces the exponent by half each iteration using bit shifts, so it runs in logarithmic time relative to the exponent.

🔧 Debug

expert

Identify the bug in fast exponentiation with modulo

This Java code attempts to compute (base^exp) % mod using fast exponentiation. Which option correctly identifies the bug causing wrong results?

DSA Java

public class PowerMod {
    public static long fastPowMod(long base, long exp, long mod) {
        long result = 1;
        base = base % mod;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exp >>= 1;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(fastPowMod(2, 10, 1000));
    }
}

A The code does not update the exponent correctly inside the loop.

B The code does not handle negative base values correctly before modulo.

C The code should use long multiplication carefully to avoid overflow before modulo.

D The code forgets to take modulo of the result after multiplication.

💡 Hint

Consider how multiplication of large numbers can overflow before modulo is applied.

Multiplying two long values can overflow before modulo is applied, causing incorrect results. Using a safe multiplication method or BigInteger is needed.

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