Fast Exponentiation Power in Log N in DSA Typescript

Mental Model

To find a number raised to a power quickly by breaking the problem into smaller parts and reusing results.

Analogy: Like folding a big paper many times by folding it in half repeatedly instead of folding it one fold at a time.

base = 2, exponent = 8
2^8
  ↓
2^4 * 2^4
  ↓
(2^2 * 2^2) * (2^2 * 2^2)
  ↓
((2^1 * 2^1) * (2^1 * 2^1)) * ((2^1 * 2^1) * (2^1 * 2^1))

Dry Run Walkthrough

Input: Calculate 2^10 using fast exponentiation

Goal: Compute 2 raised to the power 10 efficiently using repeated squaring

Step 1: Check if exponent 10 is even; since it is, split into 2^(10/2) * 2^(10/2)

2^10 -> 2^5 * 2^5

Why: Splitting the power reduces the problem size by half

Step 2: Calculate 2^5 by checking if exponent 5 is odd; split into 2 * 2^(4)

2^5 -> 2 * 2^4

Why: For odd exponents, separate one base and reduce exponent by one

Step 3: Calculate 2^4 by splitting into 2^2 * 2^2

2^4 -> 2^2 * 2^2

Why: Even exponent allows splitting to smaller powers

Step 4: Calculate 2^2 by splitting into 2^1 * 2^1

2^2 -> 2^1 * 2^1

Why: Keep splitting until exponent is 1

Step 5: Calculate 2^1 which is base case, return 2

2^1 = 2

Why: Base case stops recursion

Step 6: Multiply results: 2^2 = 2 * 2 = 4

2^2 = 4

Why: Combine smaller powers to get bigger power

Step 7: Calculate 2^4 = 4 * 4 = 16

2^4 = 16

Why: Combine results of 2^2 powers

Step 8: Calculate 2^5 = 2 * 16 = 32

2^5 = 32

Why: Multiply base with 2^(exponent-1) result for odd exponent

Step 9: Calculate 2^10 = 32 * 32 = 1024

2^10 = 1024

Why: Combine two halves of power for even exponent

Result:

2^10 = 1024

Annotated Code

DSA Typescript

class FastExponentiation {
  static power(base: number, exponent: number): number {
    if (exponent === 0) return 1; // base case: anything^0 = 1
    if (exponent % 2 === 0) {
      // even exponent
      const half = FastExponentiation.power(base, exponent / 2); // compute half power
      return half * half; // multiply halves
    } else {
      // odd exponent
      return base * FastExponentiation.power(base, exponent - 1); // reduce exponent by one
    }
  }
}

// Driver code
const base = 2;
const exponent = 10;
const result = FastExponentiation.power(base, exponent);
console.log(`${base}^${exponent} = ${result}`);

if (exponent === 0) return 1; // base case: anything^0 = 1

stop recursion when exponent is zero

if (exponent % 2 === 0) {

check if exponent is even to split power

const half = FastExponentiation.power(base, exponent / 2);

recursively compute half power

return half * half;

combine two halves for even exponent

return base * FastExponentiation.power(base, exponent - 1);

handle odd exponent by reducing it by one

Output

2^10 = 1024

Complexity Analysis

Time: O(log n) because the exponent is divided by 2 each recursive call

Space: O(log n) due to recursion call stack depth proportional to log n

vs Alternative: Naive approach is O(n) by multiplying base exponent times, which is slower for large exponents

Edge Cases

exponent = 0

returns 1 immediately as base case

DSA Typescript

if (exponent === 0) return 1;

exponent = 1

returns base directly after one recursive call

DSA Typescript

return base * FastExponentiation.power(base, exponent - 1);

base = 0 and exponent > 0

returns 0 as 0 raised to any positive power is 0

DSA Typescript

handled naturally by recursion and multiplication

When to Use This Pattern

When you need to compute large powers quickly, look for fast exponentiation using repeated squaring to reduce time from linear to logarithmic.

Common Mistakes

Mistake: Not handling the base case exponent = 0, causing infinite recursion
Fix: Add a condition to return 1 when exponent is zero

Mistake: Multiplying base repeatedly without splitting exponent, causing O(n) time
Fix: Use exponent halving and recursive calls to achieve O(log n) time

Summary

Computes base raised to exponent quickly by splitting exponent in half repeatedly.

Use when you need fast power calculation especially for large exponents.

The key insight is to reduce the problem size by half each step using repeated squaring.

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