Pow(x, n)

Pow(x, n) asks you to compute one number raised to a power. It sounds easy. Just multiply in a loop, right? But the interviewer wants the fast version. They also want to see you handle a negative power without breaking. That is where most people slip.

🎯 The Problem

You get a number x and a whole number n, and return x raised to the power n.

The rules:

• The power n can be positive, zero, or negative.
• A negative exponent means one divided by the positive power. So x^-n is 1 / x^n.
• A power of zero gives 1.
• The base x is a floating point number.

Let us try x = 2.0 and n = 10. That means 2 multiplied by itself ten times. The answer is 1024. If n were -2, the answer would be 1 / (x * x).

Input:  x = 2.0, n = 10
Output: 1024.0

Explanation: 2 multiplied by itself 10 times is 1024

The tricky part is the negative power. A negative exponent means you flip the result. So x^-n is the same as 1 / x^n. We compute the positive power first. Then we take its reciprocal.

Here is the plain idea of raising 2 to the power 10 by simple multiplication.

🐢 Approach 1: Repeated Multiply (Brute Force)

The idea:

• Start with a result of 1.
• Multiply it by x a total of n times.
• After the loop, the result holds x^n.

How it handles a negative power:

• Compute the positive power the same way.
• Then return 1 divided by that.

Why it is weak:

• If n is one million, you do one million multiplications.
• That is O(n) time.
• For large powers it is too slow.

Here is the repeated-multiply code:

def my_pow(x, n):
    if n < 0:
        x = 1 / x
        n = -n

    answer = 1
    for _ in range(n):
        answer *= x
    return answer

🧭 Approach 2: Recursive Divide and Conquer (Better)

The idea in one line: x^n is (x^(n/2))^2, so solve half the power and square the result.

How it works:

• Compute half = x^(n/2) by calling the same function on n/2.
• If n is even, the answer is half * half.
• If n is odd, the answer is half * half * x, the one extra factor.
• The base case is n = 0, which returns 1.

Why it is better:

• Each call halves the power, so the depth is about log n.
• That is O(log n) time, far fewer multiplications than the loop.

Why it is not the top pick:

• The recursion uses a call stack of depth log n, so space is O(log n).
• The loop version below does the same work with O(1) space.

Here is the recursive divide-and-conquer code:

def my_pow(x, n):
    if n == 0:
        return 1
    if n < 0:
        return 1 / my_pow(x, -n)

    half = my_pow(x, n // 2)
    if n % 2 == 0:
        return half * half
    return half * half * x

⚡ Approach 3: Exponentiation by Squaring, Loop (Best)

The idea in one line: square the base and halve the power each round, peeling off one factor when the power is odd.

How it works:

• This is called exponentiation by squaring.
• Walk while n is greater than zero.
• When the power is odd, multiply the current base into the result.
• Square the base, then halve the power with integer division.

Why it is fast:

• Each round cuts the power in half, so it takes about log n steps.
• For a power of one million that is around twenty steps, not a million.
• It uses only a few variables, so the space is O(1).

How it handles a negative power:

• Flip n to positive first and replace x with 1 / x.
• At the end the result already has the right sign.

This diagram shows the power being halved each round until it reaches zero.

Steps to Solve

1. If n is negative, set x to 1 / x and make n positive.
2. Start the result at 1.
3. While n is greater than zero, check if n is odd.
4. If n is odd, multiply the result by the current base.
5. Square the base, and halve n using integer division.
6. When n reaches zero, return the result.

#include <stdio.h>

double myPow(double x, int n) {
    long p = n;          // copy into long to flip safely
    if (p < 0) {
        x = 1 / x;       // negative power means reciprocal
        p = -p;
    }
    double result = 1.0;
    while (p > 0) {
        if (p % 2 == 1) {    // power is odd
            result *= x;     // peel off one factor
        }
        x *= x;              // square the base
        p /= 2;              // halve the power
    }
    return result;
}

int main(void) {
    printf("%g\n", myPow(2.0, 10));
    return 0;
}

1024

#include <iostream>
using namespace std;

double myPow(double x, int n) {
    long p = n;          // copy into long to flip safely
    if (p < 0) {
        x = 1 / x;       // negative power means reciprocal
        p = -p;
    }
    double result = 1.0;
    while (p > 0) {
        if (p % 2 == 1) {    // power is odd
            result *= x;     // peel off one factor
        }
        x *= x;              // square the base
        p /= 2;              // halve the power
    }
    return result;
}

int main() {
    cout << myPow(2.0, 10) << endl;
    return 0;
}

1024

public class PowXN {
    static double myPow(double x, int n) {
        long p = n;          // copy into long to flip safely
        if (p < 0) {
            x = 1 / x;       // negative power means reciprocal
            p = -p;
        }
        double result = 1.0;
        while (p > 0) {
            if (p % 2 == 1) {    // power is odd
                result *= x;     // peel off one factor
            }
            x *= x;              // square the base
            p /= 2;              // halve the power
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(myPow(2.0, 10));
    }
}

1024.0

def my_pow(x, n):
    if n < 0:
        x = 1 / x        # negative power means reciprocal
        n = -n
    result = 1.0
    while n > 0:
        if n % 2 == 1:   # power is odd
            result *= x  # peel off one factor
        x *= x           # square the base
        n //= 2          # halve the power
    return result


print(my_pow(2.0, 10))

1024.0

function myPow(x, n) {
  if (n < 0) {
    x = 1 / x;          // negative power means reciprocal
    n = -n;
  }
  let result = 1.0;
  while (n > 0) {
    if (n % 2 === 1) {  // power is odd
      result *= x;      // peel off one factor
    }
    x *= x;             // square the base
    n = Math.floor(n / 2); // halve the power
  }
  return result;
}

console.log(myPow(2.0, 10));

1024

Let us walk through the Python version line by line.

if n < 0:
    x = 1 / x
    n = -n

This handles the negative power first. A negative exponent means one divided by the positive power. So we flip the base to its reciprocal. Then we make n positive. Now the rest of the code only deals with a positive power. That keeps the loop simple.

result = 1.0

We start the answer at 1.0. Anything multiplied by one stays the same. So one is the safe starting point for building up a product.

while n > 0:
    if n % 2 == 1:
        result *= x
    x *= x
    n //= 2

This is the heart of the trick. n % 2 == 1 checks if the power is odd. If it is odd, we multiply the current base into the result. That peels off one factor of x. Then x *= x squares the base. So the base now covers twice the power it did before. And n //= 2 halves the power with integer division. Each round the power gets cut in half. So the loop runs about log n times instead of n times.

return result

When n reaches zero, every factor has been folded into result. So we return it. If the power was negative, the reciprocal at the start already took care of the sign.

⏱️ Time and Space Complexity

The brute force does one multiplication per unit of power, so it is O(n) time. The squaring method halves the power every round, so it runs in O(log n) time. Both use only a few variables, so the space is O(1). The squaring method wins big for large powers.

🧩 Key Takeaways

• ✅ A negative power means one divided by the positive power, so flip the base first.
• ✅ The brute force multiplies n times, which is slow for large powers.
• ✅ Exponentiation by squaring halves the power each round, giving O(log n) time.
• ✅ When the power is odd, peel off one factor into the result, then keep squaring.
• ✅ Copy the power into a wider type before flipping its sign to avoid overflow.

🚀 What’s Next?

• Happy Number
• Detect Squares