Pow(x, n)

One of the most common interview questions involving recursion, mathematics, and binary thinking is implementing the power function efficiently.

Problem

Implement:

pow(x, n)

which calculates:

xⁿ

without using built-in power functions.

---

Brute Force Approach

Multiply x exactly n times.

double ans = 1.0;

for(int i = 0; i < n; i++) {
    ans *= x;
}

Complexity

• Time: O(n)
• Space: O(1)

This works for small values but becomes inefficient when n is very large.

---

Key Observation

Let's calculate:

2¹⁰

Instead of multiplying 2 ten times:

2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2

we can use:

2¹⁰ = (2²)⁵

and

2² = 4
2⁴ = 16
2⁸ = 256

We're reducing the exponent by half every time.

This is called Binary Exponentiation.

---

Intuition

For every exponent:

If exponent is even

xⁿ = (x²)ⁿᐟ²

Example:

2¹⁰
→ 4⁵

If exponent is odd

Take one x into the answer and reduce exponent by one.

2⁵
→ 2 × 2⁴

---

Optimal Solution

class Solution {
    public double myPow(double x, int n) {

        long power = n;
        double ans = 1.0;

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

        while (power > 0) {

            if (power % 2 == 0) {
                x *= x;
                power /= 2;
            } else {
                ans *= x;
                power--;
            }
        }

        return ans;
    }
}

---

Dry Run

Input:

x = 2
n = 10

Initial:

ans = 1

Step 1:

10 is even

x = 4
power = 5

Step 2:

5 is odd

ans = 4
power = 4

Step 3:

4 is even

x = 16
power = 2

Step 4:

2 is even

x = 256
power = 1

Step 5:

1 is odd

ans = 1024
power = 0

Answer:

1024

---

Important Edge Case

Consider:

n = Integer.MIN_VALUE;

-2147483648

Doing:

n = -n;

causes overflow because:

2147483648

cannot fit inside an integer.

Therefore always store the exponent in:

long power = n;

before negating it.

---

Complexity Analysis

Time Complexity

O(log n)

The exponent is halved at every step.

Space Complexity

O(1)

---

Interview Takeaway

Whenever you see:

aᵇ

think:

Can I process the exponent bit by bit?

Binary Exponentiation is a powerful pattern that appears in:

• Fast Power
• Matrix Exponentiation
• Modular Arithmetic
• Competitive Programming
• System Design Calculations

Remember:

Odd exponent  -> Take one x into answer
Even exponent -> Square x and halve exponent

That's the entire algorithm.

I'm currently solving the Striver SDE Sheet Challenge and documenting my learnings, patterns, mistakes, and interview insights along the way.

LinkedIn: https://www.linkedin.com/in/jaspreetsodhi482/
X (Twitter): https://x.com/Jaspree54799902
GitHub: https://github.com/codewithjaspreet