LeetCode #50 Pow(x, n)

Medium

Problem

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

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.10000, 3
Output: 9.26100

Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Note:

• -100.0 < x < 100.0
• n is a 32-bit signed integer, within the range [−2^31, 2^31 − 1]

Solution — Recursion

It’s clear that we can divide n in half at each recursive call.

Complexity

It’s trivial that time complexity is O(logn) because we divide n in half each time.

However, calls in calling stack may also reach O(logn) as well, so it uses O(logn) extra space.

Solution — Iteration

We can treat n as binary and pick corresponding value into result when corresponding digit is 1. For example, if n = 19, it’s binary presentation is 10011, which means we can only pick x^(2^0), x^(2^1) and x^(2^4) into result.

Complexity

It takes O(logn) time to iterate all digits of n’s binary presentation, so it’s time complexity is O(logn). And it’s clear that it only uses O(1) extra space.