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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to return 1 when the exponent is zero.

DSA Javascript

function power(base, exponent) {
  if (exponent === 0) {
    return [1];
  }
  return base * power(base, exponent - 1);
}

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

Aexponent

B0

Cbase

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Returning 0 instead of 1 for exponent 0.

The power of any number to the zero is 1.

2fill in blank

medium

Complete the code to check if the exponent is even.

DSA Javascript

function power(base, exponent) {
  if (exponent === 0) {
    return 1;
  }
  if (exponent [1] 2 === 0) {
    let half = power(base, exponent / 2);
    return half * half;
  } else {
    return base * power(base, exponent - 1);
  }
}

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

A%

B===

C!==

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using '===' instead of '%' to check evenness.

Using modulus (%) operator with 2 checks if the exponent is even.

3fill in blank

hard

Fix the error in the recursive call to correctly compute half power.

DSA Javascript

function power(base, exponent) {
  if (exponent === 0) {
    return 1;
  }
  if (exponent % 2 === 0) {
    let half = power(base, [1]);
    return half * half;
  } else {
    return base * power(base, exponent - 1);
  }
}

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

Aexponent / 2

Bexponent + 1

Cexponent - 1

Dexponent * 2

Attempts:

3 left

💡 Hint

Common Mistakes

Using exponent * 2 or exponent - 1 instead of exponent / 2.

For even exponent, we compute power(base, exponent / 2) once and square it.

4fill in blank

hard

Fill both blanks to optimize the power function using fast exponentiation.

DSA Javascript

function power(base, exponent) {
  if (exponent === 0) {
    return 1;
  }
  if (exponent [1] 2 === 0) {
    let half = power(base, exponent [2] 2);
    return half * half;
  } else {
    return base * power(base, exponent - 1);
  }
}

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

A%

B/

C*

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using '*' or '-' instead of '/' for division.

Use '%' to check evenness and '/' to divide exponent by 2.

5fill in blank

hard

Fill all three blanks to implement fast exponentiation with memoization.

DSA Javascript

function power(base, exponent, memo = {}) {
  if (exponent === 0) {
    return 1;
  }
  if (memo[exponent]) {
    return memo[exponent];
  }
  if (exponent [1] 2 === 0) {
    let half = power(base, exponent [2] 2, memo);
    memo[exponent] = half * half;
  } else {
    memo[exponent] = base * power(base, exponent [3], memo);
  }
  return memo[exponent];
}

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

A%

B/

C- 1

D+ 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using '+ 1' instead of '- 1' for odd exponent.

Use '%' to check evenness, '/' to divide exponent by 2, and '- 1' to reduce exponent in odd case.

Practice

1. What is the main advantage of using Fast Exponentiation to calculate baseexponent compared to simple repeated multiplication?

easy

A. It only works for exponents that are powers of two.

B. It uses less memory by storing all intermediate powers.

C. It avoids multiplication completely by using addition.

D. It reduces the number of multiplications from linear to logarithmic in the exponent.

Solution

1. Step 1: Understand simple repeated multiplication

   Calculating baseexponent by multiplying base by itself exponent times takes exponent multiplications, which is linear time.

2. Step 2: Understand fast exponentiation approach

   Fast exponentiation reduces multiplications by squaring results and halving the exponent, achieving logarithmic time complexity.

3. Final Answer:

   It reduces the number of multiplications from linear to logarithmic in the exponent. -> Option D

4. Quick Check:

   Fast exponentiation = fewer multiplications [OK]

Hint: Fast exponentiation halves exponent steps, speeding up power calculation [OK]

Common Mistakes:

• Thinking it avoids multiplication entirely
• Believing it only works for powers of two
• Confusing memory use with speed

2. Which of the following JavaScript function definitions correctly implements fast exponentiation for positive integers?

easy

A. function power(base, exp) { if (exp === 0) return 1; let half = power(base, Math.floor(exp / 2)); return exp % 2 === 0 ? half * half : half * half * base; }

B. function power(base, exp) { let result = 1; for (let i = 0; i < exp; i++) { result *= base; } return result; }

C. function power(base, exp) { return base ** exp; }

D. function power(base, exp) { if (exp === 1) return base; return power(base, exp - 1) * base; }

Solution

1. Step 1: Identify fast exponentiation pattern

   Fast exponentiation uses recursion with halving the exponent and squaring intermediate results.

2. Step 2: Check each function

   function power(base, exp) { if (exp === 0) return 1; let half = power(base, Math.floor(exp / 2)); return exp % 2 === 0 ? half * half : half * half * base; } uses recursion, halves the exponent, and squares results correctly. The other options use linear multiplication or built-in operator, not fast exponentiation.

3. Final Answer:

   implements fast exponentiation correctly. -> Option A

4. Quick Check:

   Recursion + halving exponent = fast exponentiation [OK]

Hint: Look for recursion with exponent halving and squaring [OK]

Common Mistakes:

• Choosing simple loops instead of recursion
• Using built-in power operator without algorithm
• Confusing base case conditions

3. What is the output of the following JavaScript code?

function fastPower(base, exp) {
  if (exp === 0) return 1;
  let half = fastPower(base, Math.floor(exp / 2));
  if (exp % 2 === 0) return half * half;
  else return half * half * base;
}
console.log(fastPower(2, 5));

medium

A. 32

B. 25

C. 16

D. 10

Solution

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

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

2. Step 2: Calculate values bottom-up

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

3. Final Answer:

   32 -> Option A

4. Quick Check:

   2^5 = 32 [OK]

Hint: Trace recursion bottom-up, square halves, multiply base if odd [OK]

Common Mistakes:

• Calculating 2^5 as 16 by squaring only once
• Confusing exponent halving with division
• Missing multiplication by base when exponent is odd

4. The following code attempts to implement fast exponentiation but has a bug. What is the bug?

function fastPower(base, exp) {
  if (exp === 0) return 1;
  let half = fastPower(base, exp / 2);
  if (exp % 2 === 0) return half * half;
  else return half * half * base;
}

medium

A. The base case should return 0 instead of 1.

B. The exponent is not floored before recursive call, causing infinite recursion for odd exponents.

C. The multiplication order is incorrect for odd exponents.

D. The function does not handle negative exponents.

Solution

1. Step 1: Analyze recursive call argument

   The recursive call uses exp / 2 without flooring, so for odd exponents it passes a decimal, causing infinite recursion.

2. Step 2: Identify fix

   Using Math.floor(exp / 2) ensures the exponent decreases properly and recursion ends.

3. Final Answer:

   The exponent is not floored before recursive call, causing infinite recursion for odd exponents. -> Option B

4. Quick Check:

   Floor exponent before recursion to avoid infinite calls [OK]

Hint: Always floor exponent division in recursion [OK]

Common Mistakes:

• Ignoring decimal exponents in recursion
• Changing base case return value incorrectly
• Assuming multiplication order causes bugs

5. You want to compute 313 modulo 7 efficiently using fast exponentiation. Which of the following code snippets correctly implements this with modulo at each multiplication step to avoid large numbers?

hard

A. function modPower(base, exp, mod) {
if (exp === 0) return 0;
return (base * modPower(base, exp - 1, mod)) % mod;
}
console.log(modPower(3, 13, 7));

B. function modPower(base, exp, mod) {
let result = 1;
for (let i = 0; i < exp; i++) {
result = (result * base) % mod;
}
return result;
}
console.log(modPower(3, 13, 7));

C. function modPower(base, exp, mod) {
if (exp === 0) return 1;
let half = modPower(base, Math.floor(exp / 2), mod);
let halfSquared = (half * half) % mod;
if (exp % 2 === 0) return halfSquared;
else return (halfSquared * base) % mod;
}
console.log(modPower(3, 13, 7));

D. function modPower(base, exp, mod) {
return (base ** exp) % mod;
}
console.log(modPower(3, 13, 7));

Solution

1. Step 1: Understand modulo in fast exponentiation

   Modulo must be applied after each multiplication to keep numbers small and correct.

2. Step 2: Check each option

   function modPower(base, exp, mod) { if (exp === 0) return 1; let half = modPower(base, Math.floor(exp / 2), mod); let halfSquared = (half * half) % mod; if (exp % 2 === 0) return halfSquared; else return (halfSquared * base) % mod; } console.log(modPower(3, 13, 7)); applies modulo after squaring and multiplication recursively. function modPower(base, exp, mod) { let result = 1; for (let i = 0; i < exp; i++) { result = (result * base) % mod; } return result; } console.log(modPower(3, 13, 7)); uses linear loop (correct but slower). function modPower(base, exp, mod) { if (exp === 0) return 0; return (base * modPower(base, exp - 1, mod)) % mod; } console.log(modPower(3, 13, 7)); returns 0 for base case (wrong). function modPower(base, exp, mod) { return (base ** exp) % mod; } console.log(modPower(3, 13, 7)); uses built-in power without modulo at each step (incorrect for large exponents).

3. Final Answer:

   correctly implements fast exponentiation with modulo at each step. -> Option C

4. Quick Check:

   Modulo after each multiply keeps numbers small [OK]

Hint: Apply modulo after every multiplication step [OK]

Common Mistakes:

• Not applying modulo at intermediate steps
• Wrong base case returning 0
• Using built-in power without modulo