Pow(x, n)

NeetCode: Pow(x, n) · LeetCode: 50. Pow(x, n) · Difficulty: Medium

Implement pow(x, n) for a double x and a 32-bit signed integer n. n may be negative.

Example

Text

Input:  x = 2.0, n = 10     Output: 1024.0
Input:  x = 2.0, n = -2     Output: 0.25
Input:  x = 2.0, n = 0      Output: 1.0

Brute force: multiply n times

x^n is x multiplied by itself n times. For a negative n, compute x^|n| and take the reciprocal. Convert n to long before negating or taking the absolute value, because Integer.MIN_VALUE has no positive int counterpart: -Integer.MIN_VALUE and Math.abs(Integer.MIN_VALUE) both stay negative. The loop takes |n| steps, which is billions for n near 2^31 and exceeds LeetCode's time limit, so the demo uses small exponents.

The demo prints with String.format(Locale.ROOT, "%.5f", value), which fixes five decimals and a . separator regardless of the machine's locale.

Java

import java.util.Locale;

class Solution {
    public double myPow(double x, int n) {
        long times = Math.abs((long) n);
        double result = 1.0;
        for (long i = 0; i < times; i++) {
            result *= x;
        }
        return n < 0 ? 1.0 / result : result;
    }
}

public class Main {
    static String show(double v) {
        return String.format(Locale.ROOT, "%.5f", v);
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(show(s.myPow(2.0, 10)));
        System.out.println(show(s.myPow(2.0, -2)));
        System.out.println(show(s.myPow(2.0, 0)));
        System.out.println(show(s.myPow(2.1, 3)));
    }
}

Output

Time: O(|n|). Space: O(1).

Optimal: exponentiation by squaring

Write n in binary. Since x^n is the product of x^(2^k) over the set bits k of n, keep a base that is squared every round (x, x², x⁴, x⁸, ...) and multiply it into the result whenever the current lowest bit of n is 1. For example x^10 with 10 = 1010₂ multiplies in x² and x⁸.

bit of `n`	base	result
0	`x`	`1`
1	`x²`	`x²`
0	`x⁴`	`x²`
1	`x⁸`	`x¹⁰`

For negative n, replace x by 1/x and n by -n up front, computing -n in long so Integer.MIN_VALUE is safe. The loop runs at most 32 rounds, one per bit of n. exp >>= 1 shifts the bits right by one, and exp & 1 reads the lowest bit.

Java

import java.util.Locale;

class Solution {
    public double myPow(double x, int n) {
        long exp = n;
        double base = x;
        if (exp < 0) {
            base = 1.0 / base;
            exp = -exp;
        }
        double result = 1.0;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result *= base;
            }
            base *= base;
            exp >>= 1;
        }
        return result;
    }
}

public class Main {
    static String show(double v) {
        return String.format(Locale.ROOT, "%.5f", v);
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(show(s.myPow(2.0, 10)));
        System.out.println(show(s.myPow(2.0, -2)));
        System.out.println(show(s.myPow(2.0, 0)));
        System.out.println(show(s.myPow(2.1, 3)));
        System.out.println(show(s.myPow(1.0, Integer.MIN_VALUE)));
        System.out.println(show(s.myPow(2.0, Integer.MIN_VALUE)));
    }
}

Output

Time: O(log |n|). Space: O(1).

For 2.0 and Integer.MIN_VALUE the base becomes 0.5 and keeps squaring until it underflows to 0.0, so the printed result is 0.00000.