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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to multiply the result by base when exponent is odd.

DSA Typescript

if (exponent % 2 !== 0) {
  result = result [1] base;
}

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 or subtraction which changes the value incorrectly.

When exponent is odd, multiply the current result by the base to include the extra factor.

2fill in blank

medium

Complete the code to halve the exponent in each step.

DSA Typescript

exponent = exponent [1] 1;

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

A>>

B-

C+

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Using normal division which results in float.

Using multiplication or subtraction which changes the exponent incorrectly.

Halving the exponent is done by integer division by 2 to reduce the problem size.

3fill in blank

hard

Fix the error in updating base by squaring it.

DSA Typescript

base = base [1] base;

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 or subtraction which changes the value incorrectly.

To square the base, multiply it by itself.

4fill in blank

hard

Fill both blanks to complete the while loop condition and the loop body update.

DSA Typescript

while (exponent [1] 0) {
  if (exponent % 2 !== 0) {
    result = result * base;
  }
  base = base * base;
  exponent = exponent [2] 1;
}

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

A>

B>>

C>=

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>=' for the condition causes an infinite loop.

Using '/' which may produce floating point results.

The loop continues while exponent is greater than zero, and exponent is halved using right shift (integer division by 2).

5fill in blank

hard

Fill all three blanks to complete the fast exponentiation function.

DSA Typescript

function fastPower(base: number, exponent: number): number {
  let result = 1;
  while (exponent [1] 0) {
    if (exponent % 2 !== 0) {
      result = result [2] base;
    }
    base = base [3] base;
    exponent = Math.floor(exponent / 2);
  }
  return result;
}

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

A>

B*

C+

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition or subtraction instead of multiplication.

Using wrong loop condition causing infinite or no loops.

The loop runs while exponent is greater than zero, multiply result by base when exponent is odd, and square the base each iteration.

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