Fast Exponentiation Power in Log N in DSA Typescript - Execution Trace

Concept Flow - Fast Exponentiation Power in Log N

Start with base and exponent

↓

Check if exponent == 0?

Yes→Return 1

No↓

Is exponent even?

Yes→Square base, halve exponent

↓

Repeat with new base and exponent

↓

Multiply result by base

↓

Reduce exponent by 1

↓

Repeat until exponent == 0

↓

Return final result

This flow shows how fast exponentiation reduces the exponent by squaring the base when even, and multiplying the result when odd, repeating until exponent is zero.

Execution Sample

DSA Typescript

function power(base: number, exp: number): number {
  let result = 1;
  while (exp > 0) {
    if (exp % 2 === 1) result *= base;
    base *= base;
    exp = Math.floor(exp / 2);
  }
  return result;
}

Calculates base raised to exp using fast exponentiation in logarithmic time.

Execution Table

Step	Operation	base	exp	result	Action Description
1	Start	2	10	1	Initialize base=2, exp=10, result=1
2	Check exp even?	2	10	1	exp=10 is even, skip multiply
3	Square base	4	10	1	base = 2*2 = 4
4	Halve exp	4	5	1	exp = 10/2 = 5
5	Check exp odd?	4	5	1	exp=5 is odd, multiply result by base
6	Multiply result	4	5	4	result = 1*4 = 4
7	Square base	16	5	4	base = 4*4 = 16
8	Halve exp	16	2	4	exp = 5//2 = 2
9	Check exp even?	16	2	4	exp=2 is even, skip multiply
10	Square base	256	2	4	base = 16*16 = 256
11	Halve exp	256	1	4	exp = 2/2 = 1
12	Check exp odd?	256	1	4	exp=1 is odd, multiply result by base
13	Multiply result	256	1	1024	result = 4*256 = 1024
14	Square base	65536	1	1024	base = 256*256 = 65536
15	Halve exp	65536	0	1024	exp = 1//2 = 0
16	End	65536	0	1024	exp=0 stop, return result=1024

💡 exp reaches 0, loop ends, final result returned

Variable Tracker

Variable	Start	After Step 3	After Step 7	After Step 10	After Step 14	Final
base	2	4	16	256	65536	65536
exp	10	10	5	2	1	0
result	1	1	4	4	1024	1024

Key Moments - 3 Insights

Why do we square the base when the exponent is even instead of multiplying the result?

When exponent is even (see Step 2 and 9), we square the base and halve the exponent to reduce steps quickly without changing the result yet. Multiplying result only happens when exponent is odd (Step 5 and 12).

Why do we multiply the result by base only when exponent is odd?

Because odd exponent means one extra base multiplication is needed before halving exponent. This is shown in Steps 5-6 and 12-13 where result updates only if exponent is odd.

Why does the loop stop when exponent reaches zero?

Exponent zero means base^0 = 1, so no more multiplication needed. The loop ends at Step 16 when exp=0 and returns the final result.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of 'result' after Step 6?

A 16

B 1

C 4

D 256

💡 Hint

Check the 'result' column at Step 6 in the execution_table.

At which step does the exponent first become odd?

A Step 2

B Step 5

C Step 4

D Step 7

💡 Hint

Look at the 'exp' and 'Operation' columns around Steps 4 and 5.

If the initial exponent was 9 instead of 10, how would the first multiplication step change?

A It would multiply result by base at the first check since 9 is odd

B It would multiply result by base immediately at Step 2

C It would skip multiplication until exponent halves to 4

D No multiplication would happen until exponent is zero

💡 Hint

Recall multiplication happens only when exponent is odd, see Steps 5 and 12.

Concept Snapshot

Fast Exponentiation (Power in Log N):
- Use base and exponent inputs
- While exponent > 0:
  - If exponent odd: multiply result by base
  - Square base
  - Halve exponent (floor division)
- Return result
This reduces steps from N to log N by squaring and halving exponent.

Full Transcript

Fast exponentiation calculates power by reducing the exponent quickly. It checks if exponent is zero to stop. If exponent is even, it squares the base and halves the exponent without changing the result. If exponent is odd, it multiplies the result by the base first, then proceeds. This repeats until exponent reaches zero, returning the final result. This method runs in logarithmic time, much faster than multiplying base exponent times.

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