m0050.md

Pow-x-n

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

• Example 1:
  • Input: x = 2.00000, n = 10
  • Output: 1024.00000
• Example 2:
  • Input: x = 2.10000, n = 3
  • Output: 9.26100
• Example 3:
  • 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
• -10^4 <= x^n <= 10^4

Solving Idea

Suppose we can only implement for now a naive pow function, which can calculate any base to the power n (n = 0, 1, 2), then 3^11 can be seen as sqr(3^5) * 3^1, and 3^10 as sqr(3^5) * 3^0, where sqr is the square function. This expression now contains 3^5 instead of 3^11, which can be disassembled recursively.

What we need now however, is a machine which can be tranformed from one state to another, and eventually a product of naive pows: square(x^m) * x or square(x^m) * 1, where x is the base provided and m < n (n is the provided power).

The calculus square(y) * x or square(y) * 1 involves three elements:

1. the original base x
2. power of the second multiplier i.e. 0 or 1
3. new base y

We donate this calculus as f, and regarding our example, 3^11 = f(3, 1, 3^5), 3^5 = f(3, 1, 3^2), and finally 3^2 = f(3, 0, 3). We can record the second argument all the way through the disassembling process: (0, 1, 1).

Now we can go back up as every argument is a known number: first we need to pick up the sequence we saved, which can be applied to f as the second argument, and for the third argument the initial value is always the same with the original base x:

1. f(3, 0, 3) = 9
2. f(3, 1, 9) = 243
3. f(3, 1, 243) = 177147

Source Code

python