Fast Exponentiation Power in Log N in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind Fast Exponentiation (Power) algorithm?

It reduces the number of multiplications by using the property that x^n = (x^(n/2))^2 when n is even, and x^n = x * x^(n-1) when n is odd, allowing calculation in logarithmic time.

beginner

Why is Fast Exponentiation faster than the naive method?

Because it uses repeated squaring to halve the exponent at each step, reducing the time complexity from O(n) to O(log n).

intermediate

In Fast Exponentiation, what happens when the exponent is odd?

We multiply the result by the base once and then reduce the exponent by 1 to make it even, continuing with repeated squaring.

beginner

Show the TypeScript function signature for Fast Exponentiation.

function fastPower(base: number, exponent: number): number

beginner

What is the time complexity of Fast Exponentiation and why?

O(log n) because the exponent is divided by 2 at each step, drastically reducing the number of multiplications needed.

What is the time complexity of Fast Exponentiation?

A O(log n)

B O(n)

C O(n^2)

D O(1)

Fast Exponentiation reduces the exponent by half each step, so it runs in O(log n) time.

In Fast Exponentiation, if the exponent is even, what is the next step?

A Multiply result by base and reduce exponent by 1

B Add 1 to the exponent

C Square the base and halve the exponent

D Return 1 immediately

When exponent is even, we square the base and halve the exponent to reduce the problem size.

What does Fast Exponentiation compute?

A Product of two numbers

B Power of a number (base^exponent)

C Sum of numbers

D Square root of a number

Fast Exponentiation efficiently computes base raised to the power of exponent.

Which of these is a key step in Fast Exponentiation when exponent is odd?

A Multiply result by base once and reduce exponent by 1

B Ignore the odd exponent

C Double the exponent

D Divide base by 2

For odd exponent, multiply result by base once and then reduce exponent by 1 to make it even.

Which of these best describes the Fast Exponentiation algorithm?

A Sorting algorithm

B Iterative addition

C Linear search

D Repeated squaring and multiplication

Fast Exponentiation uses repeated squaring and multiplication to compute power efficiently.

Explain how Fast Exponentiation reduces the number of multiplications compared to the naive method.

Think about how the exponent changes each step.

Describe the steps of the Fast Exponentiation algorithm when given a base and an exponent.

Focus on how the exponent changes and what happens to the result.

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