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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fast Exponentiation Function

What is the output of the following TypeScript function when computing power(3, 5)?

DSA Typescript

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

console.log(power(3, 5));

A 81

B 125

C 243

D 15

💡 Hint

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

The function uses fast exponentiation by dividing the exponent by 2 recursively. 3^5 = 3 * 3^4 = 3 * (3^2)^2 = 3 * (9)^2 = 3 * 81 = 243.

🧠 Conceptual

intermediate

Time Complexity of Fast Exponentiation

What is the time complexity of the fast exponentiation algorithm that computes power(base, exponent) by dividing the exponent by 2 each recursive call?

A O(log n)

B O(n)

C O(n log n)

D O(1)

💡 Hint

Think about how many times you can divide the exponent by 2 before it reaches zero.

Each recursive call halves the exponent, so the number of calls is proportional to log base 2 of the exponent. Hence, the time complexity is O(log n).

🔧 Debug

advanced

Identify the Error in Fast Exponentiation Code

What error will the following TypeScript code produce when calling power(2, 3)?

DSA Typescript

function power(base: number, exponent: number): number {
  if (exponent === 0) return 1;
  let half = power(base, exponent / 2);
  if (exponent % 2 === 0) {
    return half * half;
  } else {
    return half * half * base;
  }
}

console.log(power(2, 3));

A Maximum call stack size exceeded (infinite recursion)

B SyntaxError: Unexpected token

C Returns incorrect value 8.0

D TypeError: exponent % 2 is not a function

💡 Hint

Check how the exponent is passed in recursive calls and if it is always an integer.

The recursive call uses exponent / 2 which produces a floating-point number. The base case checks for exponent === 0, but exponent never becomes exactly 0 due to fractional values, causing infinite recursion and stack overflow.

🚀 Application

advanced

Using Fast Exponentiation for Modular Power

Which option correctly implements fast exponentiation to compute (base^exponent) % mod efficiently in TypeScript?

A

function modPower(base: number, exponent: number, mod: number): number {
  if (exponent === 0) return 0;
  let half = modPower(base, Math.floor(exponent / 2), mod);
  if (exponent % 2 === 0) {
    return half * half % mod;
  } else {
    return half * half * base % mod;
  }
}

B

function modPower(base: number, exponent: number, mod: number): number {
  if (exponent === 0) return 1 % mod;
  let half = modPower(base, Math.floor(exponent / 2), mod);
  let halfSquared = (half * half) % mod;
  if (exponent % 2 === 0) {
    return halfSquared;
  } else {
    return (halfSquared * (base % mod)) % mod;
  }
}

C

function modPower(base: number, exponent: number, mod: number): number {
  if (exponent === 1) return base % mod;
  let half = modPower(base, Math.floor(exponent / 2), mod);
  if (exponent % 2 === 0) {
    return (half * half) % mod;
  } else {
    return (half * half * base) % mod;
  }
}

D

function modPower(base: number, exponent: number, mod: number): number {
  if (exponent === 0) return 1;
  let half = modPower(base, exponent / 2, mod);
  if (exponent % 2 === 0) {
    return (half * half) % mod;
  } else {
    return (half * half * base) % mod;
  }
}

💡 Hint

Make sure to handle the base case correctly and use Math.floor for exponent division.

Option B correctly handles the base case, uses Math.floor to keep exponent integer, and applies modulo at every multiplication step to avoid overflow.

❓ Predict Output

expert

Output of Fast Exponentiation with Large Exponent

What is the output of the following TypeScript code snippet?

DSA Typescript

function fastPower(base: number, exponent: number): number {
  if (exponent === 0) return 1;
  let half = fastPower(base, Math.floor(exponent / 2));
  if (exponent % 2 === 0) {
    return half * half;
  } else {
    return half * half * base;
  }
}

console.log(fastPower(2, 10));

A 2048

B 512

C 1000

D 1024

💡 Hint

Recall that 2^10 means 2 multiplied by itself 10 times.

2^10 equals 1024. The function uses fast exponentiation correctly to compute this value.

Practice

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

easy

A. It reduces the time complexity from linear to logarithmic in terms of exponent.

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

C. It avoids using multiplication altogether.

D. It only works for small exponents.

Solution

1. Step 1: Understand simple exponentiation complexity

   Simple repeated multiplication calculates a^b by multiplying a by itself b times, which takes O(b) time.

2. Step 2: Analyze fast exponentiation complexity

   Fast exponentiation uses the idea of squaring and reduces the number of multiplications to O(log b), making it much faster for large exponents.

3. Final Answer:

   It reduces the time complexity from linear to logarithmic in terms of exponent. -> Option A

4. Quick Check:

   Fast exponentiation = O(log n) time [OK]

Hint: Fast exponentiation halves exponent each step [OK]

Common Mistakes:

• Thinking it avoids multiplication
• Assuming it uses more memory
• Believing it only works for small exponents

2. Which of the following TypeScript function signatures correctly represents a fast exponentiation function for integers a and b?

easy

A. function fastPower(a: number): number

B. function fastPower(a: string, b: number): string

C. function fastPower(a: number, b: number): void

D. function fastPower(a: number, b: number): number

Solution

1. Step 1: Check parameter types

   The function needs two inputs: base a and exponent b, both numbers.

2. Step 2: Check return type

   The function returns the result of a^b, which is a number.

3. Final Answer:

   function fastPower(a: number, b: number): number -> Option D

4. Quick Check:

   Correct signature = function fastPower(a: number, b: number): number [OK]

Hint: Function needs two number inputs and returns number [OK]

Common Mistakes:

• Using string types for numbers
• Missing one parameter
• Returning void instead of number

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

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

medium

A. 25

B. 10

C. 32

D. 16

Solution

1. Step 1: Trace recursive calls for b=5

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

2. Step 2: Calculate results 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 C

4. Quick Check:

   2^5 = 32 [OK]

Hint: Remember 2^5 = 32, check recursive halving [OK]

Common Mistakes:

• Confusing multiplication order
• Forgetting to multiply by base when exponent is odd
• Incorrect base case handling

4. Identify the bug in this fast exponentiation function and select the correct fix:

function fastPower(a: number, b: number): number {
  if (b === 0) return 0;
  let half = fastPower(a, Math.floor(b / 2));
  if (b % 2 === 0) return half * half;
  else return half * half * a;
}

medium

A. Change recursive call to fastPower(a, b - 1)

B. Change base case return from 0 to 1

C. Remove the multiplication by 'a' when exponent is odd

D. Change Math.floor to Math.ceil in recursive call

Solution

1. Step 1: Check base case correctness

   When exponent is 0, a^0 should return 1, but code returns 0, which is incorrect.

2. Step 2: Identify fix for base case

   Changing return value in base case from 0 to 1 fixes the function to correctly compute powers.

3. Final Answer:

   Change base case return from 0 to 1 -> Option B

4. Quick Check:

   Base case must return 1 [OK]

Hint: Base case for exponent 0 must return 1 [OK]

Common Mistakes:

• Returning 0 for exponent 0
• Changing recursive call incorrectly
• Removing multiplication for odd exponent

5. You want to compute (3^13) % 7 efficiently using fast exponentiation with modulo to avoid large numbers. Which modification to the fastPower function is correct?

hard

A. Apply modulo after each multiplication: (half * half) % mod and (half * half * a) % mod

B. Apply modulo only once at the end of recursion

C. Apply modulo only to the base a before recursion

D. No modulo needed if exponent is small

Solution

1. Step 1: Understand modulo property in exponentiation

   To avoid large intermediate values, modulo must be applied after every multiplication step.

2. Step 2: Modify function to apply modulo after multiplications

   Applying modulo after half * half and half * half * a keeps numbers small and correct.

3. Final Answer:

   Apply modulo after each multiplication: (half * half) % mod and (half * half * a) % mod -> Option A

4. Quick Check:

   Modulo after each multiply keeps numbers small [OK]

Hint: Modulo after every multiply prevents overflow [OK]

Common Mistakes:

• Applying modulo only once at end
• Applying modulo only to base
• Ignoring modulo for small exponents