50 - Pow(x, n)

Problem

Implement pow(x, n), which calculates x raised to the power n (i.e., x^n).

Input: x = 2.00000, n = 10
Output: 1024.00000

Input: x = 2.10000, n = 3
Output: 9.26100

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2^-2 = 1/2^2 = 1/4 = 0.25

Constraints:

• -100.0 < x < 100.0
• -2^31 <= n <= 2^31 - 1
• n is an integer.
• Either x is not zero or n > 0.
• -10^4 <= x^n <= 10^4

Approach

The trick is to write n in binary. Every number is a sum of powers of two, for example 10 = 8 + 2, which is 1010 in binary. That means

x^10 = x^8 * x^2

The powers x^1, x^2, x^4, x^8, ... are easy to get one after another, because each is the square of the one before it. So we go through the bits of n from lowest to highest, squaring x at every step. x always holds x^(2^k) for the bit we are looking at. Whenever that bit is 1, we multiply the current x into res.

x = 2, n = 10 (1010)
bit 0 = 0  ->  skip           res = 1      x = 2 -> 4
bit 1 = 1  ->  res *= 4       res = 4      x = 4 -> 16
bit 2 = 0  ->  skip           res = 4      x = 16 -> 256
bit 3 = 1  ->  res *= 256     res = 1024   x = 256 -> 65536
num = 0    ->  return 1024

For a negative n, we use x^-n = 1 / x^n. We run the same loop on |n| and flip the result at the end.

Taking |n| needs care. n can be -2^31, and 2^31 does not fit in an int, so -n would overflow. Casting to int64_t before negating keeps it in range, and it goes into a uint64_t so the right shift works on a non-negative value.

class Solution {
public:
    double myPow(double x, int n) {
        bool neg = n < 0;
        uint64_t num = n < 0 ? -(int64_t)n : n;
        double res = 1;
        while(num != 0) {
            if((num & 1) == 1) {
                res *= x;
            }
            x *= x;
            num >>= 1;
        }
        return neg ? 1/res : res;
    }
};

• time: O(log n) — one iteration per bit of |n|, at most 32
• space: O(1)