Difficulty: Medium · LeetCode 50

Problem

Implement pow(x, n) — raise x to the power n. n may be negative.

Understanding the problem

Multiplying x by itself n times is O(n). Binary exponentiation observes that x^n = (x²)^(n/2), halving the exponent each step — this gives O(log n).

Intuition

If n is even: x^n = (x²)^(n//2) — square x and halve n. If n is odd: multiply the current x into result first, then halve. Negative n → invert x.

Approach

If n < 0: set x = 1/x, n = -n.
Initialize result = 1.
While n > 0: if n % 2 == 1, multiply result *= x.
Square: x *= x; halve: n //= 2.
Return result.

Naive Solution — Brute Force

Multiply x by itself n times in a loop.

Python

class Solution:
    def myPow(self, x, n):
        if n < 0:
            x = 1 / x
            n = -n

        result = 1

        for _ in range(n):
            result *= x

        return result

C++

class Solution {
public:
    double myPow(double x, int n) {
        long long N = n;  // -n overflows int when n == INT_MIN
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }

        double result = 1;

        for (long long i = 0; i < N; i++) {
            result *= x;
        }

        return result;
    }
};

Java

class Solution {
    public double myPow(double x, int n) {
        long N = n;  // -n overflows int when n == Integer.MIN_VALUE
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }

        double result = 1;

        for (long i = 0; i < N; i++) {
            result *= x;
        }

        return result;
    }
}

JavaScript

var myPow = function(x, n) {
    if (n < 0) {
        x = 1 / x;
        n = -n;
    }

    let result = 1;

    for (let i = 0; i < n; i++) {
        result *= x;
    }

    return result;
};

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

Optimized Code (Python 3)

Python

class Solution:
    def myPow(self, x, n):
        if n < 0:
            x = 1 / x
            n = -n

        result = 1

        while n:
            if n % 2 == 1:
                result *= x

            x *= x
            n //= 2

        return result

C++

class Solution {
public:
    double myPow(double x, int n) {
        long long N = n;  // -n overflows int when n == INT_MIN
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }

        double result = 1;

        while (N) {
            if (N % 2 == 1) {
                result *= x;
            }

            x *= x;
            N /= 2;
        }

        return result;
    }
};

Java

class Solution {
    public double myPow(double x, int n) {
        long N = n;  // -n overflows int when n == Integer.MIN_VALUE
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }

        double result = 1;

        while (N != 0) {
            if (N % 2 == 1) {
                result *= x;
            }

            x *= x;
            N /= 2;
        }

        return result;
    }
}

JavaScript

var myPow = function(x, n) {
    if (n < 0) {
        x = 1 / x;
        n = -n;
    }

    let result = 1;

    while (n) {
        if (n % 2 === 1) {
            result *= x;
        }

        x *= x;
        n = Math.floor(n / 2);
    }

    return result;
};

Time: O(log n) · Space: O(1)

Takeaway

Pattern — Binary Exponentiation — halve the exponent at each step by squaring the base