DEV Community

Purav Patel
Purav Patel

Posted on

Understanding Fast Power (Exponentiation by Squaring) - Pow(x, n) Step-by-Step - LeetCode 50

#datastructures #programming #beginners #learning

With Clear Diagrams + Recursive & Iterative Methods (C#)

When solving Pow(x, n) in interviews (Google, Meta, etc.), a
brute-force solution is NOT enough.

The naive way:

x * x * x * x * ... (n times)
Enter fullscreen mode Exit fullscreen mode

This takes O(n) time.

But we can do better.

We can solve it in:

O(log n)
Enter fullscreen mode Exit fullscreen mode

Let's understand this deeply --- visually and line-by-line.

🧠 The Key Mathematical Insight

If n is EVEN: 

x^n = (x^(n/2))²
Enter fullscreen mode Exit fullscreen mode

Example:

2^8
= (2^4)²
= (16)²
= 256
Enter fullscreen mode Exit fullscreen mode

Why?

Because:

2^8 = 2×2×2×2×2×2×2×2
     = (2×2×2×2) × (2×2×2×2)
     = 2^4 × 2^4
Enter fullscreen mode Exit fullscreen mode

If n is ODD: 

x^n = (x^((n-1)/2))² × x
Enter fullscreen mode Exit fullscreen mode

Example:

2^9
= 2 × 2^8
= 2 × (2^4)²
Enter fullscreen mode Exit fullscreen mode

We remove one x to make the exponent even.

🚀 Why This Is Faster

Instead of reducing:

n → n-1 → n-2 → ...
Enter fullscreen mode Exit fullscreen mode

We reduce:

n → n/2 → n/4 → n/8 → ...
Enter fullscreen mode Exit fullscreen mode

So recursion depth becomes:

O(log n)
Enter fullscreen mode Exit fullscreen mode

📘 Recursive Method (C#) 

public class Solution {
    public double MyPow(double x, int n) {
        long N = n;

        if (N < 0) {
            x = 1 / x;
            N = -N;
        }

        return FastPow(x, N);
    }

    private double FastPow(double x, long n) {
        if (n == 0) return 1;

        double half = FastPow(x, n / 2);

        if (n % 2 == 0)
            return half * half;
        else
            return half * half * x;
    }
}
Enter fullscreen mode Exit fullscreen mode

🔍 Recursive Flow Diagram (Example: 2^13) 

FastPow(2,13)
    ↓
FastPow(2,6)
    ↓
FastPow(2,3)
    ↓
FastPow(2,1)
    ↓
FastPow(2,0)
Enter fullscreen mode Exit fullscreen mode

Now it builds back up:

2^0 = 1
2^1 = 1×1×2 = 2
2^3 = 2×2×2 = 8
2^6 = 8×8 = 64
2^13 = 64×64×2 = 8192
Enter fullscreen mode Exit fullscreen mode

✔ Final Answer: 8192

🧠 What Happens in Memory (Call Stack)

At deepest recursion:

FastPow(2,13)
  FastPow(2,6)
    FastPow(2,3)
      FastPow(2,1)
        FastPow(2,0)
Enter fullscreen mode Exit fullscreen mode

Then it unwinds upward.

Maximum stack depth:

log₂(13) ≈ 4 levels
Enter fullscreen mode Exit fullscreen mode

⚡ Iterative Method (More Interview Friendly)

This avoids recursion entirely.

public double MyPow(double x, int n) {
    long N = n;

    if (N < 0) {
        x = 1 / x;
        N = -N;
    }

    double result = 1;

    while (N > 0) {
        if ((N & 1) == 1) {
            result *= x;
        }

        x *= x;
        N >>= 1;
    }

    return result;
}
Enter fullscreen mode Exit fullscreen mode

🔍 Iterative Flow (2^13)

Binary of 13:

13 = 1101₂
Enter fullscreen mode Exit fullscreen mode

We process bits from right to left:

Step N Action x becomes
1 13 (odd) result *= x x²
2 6 skip x⁴
3 3 (odd) result *= x x⁸
4 1 (odd) result *= x x¹⁶

Final result = 8192

⏱ Complexity

Method Time Complexity Space Complexity
Recursive O(log n) O(log n)
Iterative O(log n) O(1)

🎯 Final Takeaways

  • Never multiply x n times.
  • Use divide-and-conquer.
  • Always convert n to long to avoid overflow.
  • Prefer iterative version in interviews.

If this helped you understand recursion better, try implementing it
yourself without looking at the solution!

Top comments (0)