Fast Exponentiation Power in Log N in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to multiply the result by x when n is odd.

DSA Java

if (n % 2 == 1) result = result [1] x;

Drag options to blanks, or click blank then click option'

A+

B/

C*

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of multiplication.

Using division which reverses multiplication.

Using subtraction which does not accumulate powers.

When n is odd, multiply the current result by x to include the extra factor.

2fill in blank

medium

Complete the code to square x in each iteration.

DSA Java

x = x [1] x;

Drag options to blanks, or click blank then click option'

A*

B+

C-

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of multiplication.

Using division which reduces the value.

Using subtraction which changes the value incorrectly.

Squaring x means multiplying x by itself to prepare for the next power step.

3fill in blank

hard

Fix the error in the loop condition to run while n is greater than zero.

DSA Java

while (n [1] 0) {

Drag options to blanks, or click blank then click option'

A>

B<

C==

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using less than which never enters the loop if n starts positive.

Using equality which runs only if n is zero.

Using less or equal which may cause infinite loops.

The loop should continue while n is greater than zero to process all bits.

4fill in blank

hard

Fill both blanks to update n by dividing it by 2 using right shift.

DSA Java

n = n [1] 1; // shift right by 1
// or equivalently
n = n [2] 2;

Drag options to blanks, or click blank then click option'

A>>

B<<

C/

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Using left shift which multiplies by 2.

Using multiplication which increases n.

Using left shift or multiplication in place of division.

Right shift by 1 divides n by 2. Using / 2 also divides n by 2.

5fill in blank

hard

Fill all three blanks to complete the fast exponentiation method.

DSA Java

public static long fastPower(long x, long n) {
    long result = 1;
    while (n [1] 0) {
        if ((n & 1) == 1) result = result [2] x;
        x = x [3] x;
        n = n >> 1;
    }
    return result;
}

Drag options to blanks, or click blank then click option'

A>

B*

C+

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of multiplication.

Using wrong loop condition operators.

Forgetting to square x each iteration.

Loop while n > 0, multiply result by x when n is odd, and square x each iteration.

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