50. Pow(x, n) (Medium)

Problem

Implement pow(x, n), raise x to the integer power n. n can be negative. Use only basic arithmetic (don’t call a library pow).

Example

• x = 2.0, n = 10 → 1024.0
• x = 2.0, n = -2 → 0.25

LeetCode 50 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, multiply n times

Python

def my_pow(x, n):
    if n < 0:               # L1: O(1)
        x = 1 / x           # L2: O(1)
        n = -n              # L3: O(1)
    result = 1.0
    for _ in range(n):      # L4: loop |n| times
        result *= x         # L5: O(1)
    return result

TypeScript

function myPow(x: number, n: number): number {
    if (n < 0) { x = 1 / x; n = -n; }   // L1-L3: O(1)
    let result = 1.0;
    for (let i = 0; i < n; i++) result *= x;  // L4, L5: loop |n| times
    return result;
}

Go

func myPow(x float64, n int) float64 {
    if n < 0 { x = 1 / x; n = -n }   // L1-L3: O(1)
    result := 1.0
    for i := 0; i < n; i++ { result *= x }  // L4, L5: loop |n| times
    return result
}

Swift

final class Solution {
    func myPow(_ x: Double, _ n: Int) -> Double {
        let exponent = n.magnitude
        var result = 1.0
        for _ in 0..<exponent { result *= x }
        return n < 0 ? 1.0 / result : result
    }
}

Where the time goes, line by line

Variables: n = the exponent (absolute value used for iteration).

Line	Per-call cost	Times executed	Contribution
L1-L3 (sign handling)	$O(1)$	1	$O(1)$
L4, L5 (multiply loop)	$O(1)$	|n|	$O(\|n\|)$ ← dominates

Every multiplication is $O(1)$; the loop runs |n| times.

Complexity

• Time: $O(|n|)$, driven by L4/L5 (one multiply per exponent bit position).
• Space: $O(1)$.

Times out for large |n|.

Approach 2: Recursive exponentiation by squaring (canonical)

x^n = (x^(n/2))² · (x if n odd else 1).

Python

def my_pow(x, n):
    if n < 0:                           # L1: O(1)
        x = 1 / x                       # L2: O(1)
        n = -n                          # L3: O(1)

    def helper(base, exp):
        if exp == 0:
            return 1                    # L4: base case O(1)
        half = helper(base, exp // 2)   # L5: recurse on half exponent
        if exp % 2 == 0:
            return half * half          # L6: O(1)
        return half * half * base       # L7: O(1) for odd exp

    return helper(x, n)

TypeScript

function myPow(x: number, n: number): number {
    if (n < 0) {                                    // L1: O(1)
        x = 1 / x;                                 // L2: O(1)
        n = -n;                                    // L3: O(1)
    }

    function helper(base: number, exp: number): number {
        if (exp === 0) return 1;                    // L4: base case O(1)
        const half = helper(base, Math.floor(exp / 2));  // L5: recurse on half exponent
        if (exp % 2 === 0) return half * half;      // L6: O(1)
        return half * half * base;                  // L7: O(1) for odd exp
    }

    return helper(x, n);
}

Go

func myPow(x float64, n int) float64 {
    if n < 0 {                           // L1: O(1)
        x = 1 / x                        // L2: O(1)
        n = -n                           // L3: O(1)
    }
    var helper func(base float64, exp int) float64
    helper = func(base float64, exp int) float64 {
        if exp == 0 { return 1 }         // L4: base case O(1)
        half := helper(base, exp/2)      // L5: recurse on half exponent
        if exp%2 == 0 { return half * half }  // L6: O(1)
        return half * half * base        // L7: O(1) for odd exp
    }
    return helper(x, n)
}

Swift

final class Solution {
    func myPow(_ x: Double, _ n: Int) -> Double {
        let value = power(x, n.magnitude)
        return n < 0 ? 1.0 / value : value
    }

    private func power(_ base: Double, _ exponent: UInt) -> Double {
        if exponent == 0 { return 1.0 }
        let half = power(base, exponent / 2)
        return exponent.isMultiple(of: 2) ? half * half : half * half * base
    }
}

Where the time goes, line by line

Variables: n = the exponent (absolute value).

Line	Per-call cost	Times executed	Contribution
L4 (base case)	$O(1)$	1	$O(1)$
L5 (recursive halving)	$O(1)$ per level	log n levels	$O(log n)$ ← dominates
L6, L7 (squaring)	$O(1)$	log n	$O(log n)$

Each recursive call halves the exponent; there are log n levels, each doing $O(1)$ work.

Complexity

• Time: $O(log |n|)$, driven by L5 (halving the exponent at each level).
• Space: $O(log |n|)$ recursion stack depth.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Iterative exponentiation by squaring (optimal)

Python

def my_pow(x, n):
    if n < 0:               # L1: O(1)
        x = 1 / x           # L2: O(1)
        n = -n              # L3: O(1)
    result = 1.0            # L4: O(1)
    while n:                # L5: loop log n times
        if n & 1:
            result *= x     # L6: O(1), multiply in if odd bit
        x *= x              # L7: O(1), square x each iteration
        n >>= 1             # L8: O(1), shift to next bit
    return result

TypeScript

function myPow(x: number, n: number): number {
    if (n < 0) {            // L1: O(1)
        x = 1 / x;         // L2: O(1)
        n = -n;             // L3: O(1)
    }
    let result = 1.0;       // L4: O(1)
    while (n) {             // L5: loop log n times
        if (n & 1) result *= x;   // L6: O(1), multiply in if odd bit
        x *= x;             // L7: O(1), square x each iteration
        n >>= 1;            // L8: O(1), shift to next bit
    }
    return result;
}

Go

func myPow(x float64, n int) float64 {
    if n < 0 {               // L1: O(1)
        x = 1 / x            // L2: O(1)
        n = -n               // L3: O(1)
    }
    result := 1.0            // L4: O(1)
    for n != 0 {             // L5: loop log n times
        if n&1 == 1 { result *= x }  // L6: O(1), multiply in if odd bit
        x *= x               // L7: O(1), square x each iteration
        n >>= 1              // L8: O(1), shift to next bit
    }
    return result
}

Swift

final class Solution {
    func myPow(_ x: Double, _ n: Int) -> Double {
        var base = x
        var exponent = n.magnitude
        var result = 1.0
        while exponent > 0 {
            if !exponent.isMultiple(of: 2) { result *= base }
            base *= base
            exponent /= 2
        }
        return n < 0 ? 1.0 / result : result
    }
}

Where the time goes, line by line

Variables: n = the exponent (absolute value).

Line	Per-call cost	Times executed	Contribution
L1-L4 (setup)	$O(1)$	1	$O(1)$
L5-L8 (bit loop)	$O(1)$	log n	$O(log n)$ ← dominates
L6 (conditional multiply)	$O(1)$	at most log n	$O(log n)$
L7 (square)	$O(1)$	log n	$O(log n)$

The while loop iterates once per bit in n; there are log n bits.

Complexity

• Time: $O(log |n|)$, driven by L5/L6/L7/L8 (one iteration per bit of the exponent).
• Space: $O(1)$.

Why it works

Every integer n has a binary expansion. x^n = prod(x^(2^k)) over the bit positions k where n has a 1. Iterate the bits, squaring x each time; multiply into the result when the current bit is set.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Multiply n times	$O(n)$	$O(1)$
Recursive squaring	$O(log n)$	$O(log n)$
Iterative squaring	$O(log n)$	$O(1)$

Fast exponentiation is the template for modular exponentiation (common in number-theory problems), matrix exponentiation (linear recurrences), and Fast Fibonacci.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_050.py and run.
# Uses the canonical implementation (Approach 3: iterative squaring).

def my_pow(x, n):
    if n < 0:
        x = 1 / x
        n = -n
    result = 1.0
    while n:
        if n & 1:
            result *= x
        x *= x
        n >>= 1
    return result

def _run_tests():
    assert abs(my_pow(2.0, 10) - 1024.0) < 1e-9
    assert abs(my_pow(2.0, -2) - 0.25) < 1e-9
    assert abs(my_pow(2.0, 0) - 1.0) < 1e-9      # anything^0 = 1
    assert abs(my_pow(1.0, 1000000) - 1.0) < 1e-9  # large exponent on 1
    assert abs(my_pow(0.0, 5) - 0.0) < 1e-9      # 0^n = 0 for n > 0
    assert abs(my_pow(2.0, 1) - 2.0) < 1e-9
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function myPow(x: number, n: number): number {
    if (n < 0) { x = 1 / x; n = -n; }
    let result = 1.0;
    while (n) {
        if (n & 1) result *= x;
        x *= x;
        n >>= 1;
    }
    return result;
}

console.assert(Math.abs(myPow(2.0, 10) - 1024.0) < 1e-9);
console.assert(Math.abs(myPow(2.0, -2) - 0.25) < 1e-9);
console.assert(Math.abs(myPow(2.0, 0) - 1.0) < 1e-9);
console.assert(Math.abs(myPow(1.0, 1000000) - 1.0) < 1e-9);
console.assert(Math.abs(myPow(0.0, 5) - 0.0) < 1e-9);
console.assert(Math.abs(myPow(2.0, 1) - 2.0) < 1e-9);
console.log('all tests pass');

Related data structures

• Arrays, bit-based iteration (no auxiliary structure)

Related concepts

• Math and Number Theory, the arithmetic invariant behind digits, divisibility, modulo behavior, and identities.
• Divide and Conquer, the split, solve, and combine pattern for independent subproblems.