**Pow(x, n)**
Description
Implement pow(x, n)
, which calculates x raised to the power n (xn).
Example
1 | Example 1: |
Solution
The basic thought of this problem is Divide & Conquer
. We can divide it into two halves and then calculate it. For example1 n = 10
, then we can have 210 = 25 * 25, next we calculate 22 and 23, but wait a second, when n is odd, we need to calculat twice, why can’t we just calculate 22, and then 22 * 22 * 2, so based on this, we can come up with the following algorithm. This is just for x >= 0
, if x < 0
, we need to pay a little more attention.
Algorithm
My algorithm
Python
1 | def myPow(self, x, n): |
This is my algorithm, a little long, but the basic idea is correct. Let’s see a more concise one.
Concise algorithm
Python
1 | def myPow(self, x, n): |
This one is really elegant and concise…
Complexity
Time Complexity: O(log(n))
.
Space Complexity: O(1)
.