LeetCode#50 Pow(x, n)

Just...

Implement pow(x, n).

Solution:

1）Naive solution：multiply x by itself for n-1 times. (Or simply reyurn 1 if n==0).

This takes O(n) time. When n is big enough, it's relatively slow.

2）Fast Power.

Take pow(3, 11) as an example. Here's what we're gonna do:

represent 11 as a binary number, which is bn=1011. Assign x to a new variable base=x, and set result as 1.

iterate digits in bn from rear to head,

1._if the current digit is 1, result is multiplied by base;

2._if the current digit is 0, result will remain unchanged;

3._alter base: base=base * base.

The reversed iteration of binary digits can alse be replaced by a series of dived-and-mod operations on n.

Mathematics behind it:

Each n has a baniry version. And we know: pow(a, m+n)=pow(a, m)*pow(a, n).

Thus pow(3, 11)=pow(3, 1)*pow(3, 2)*pow(3, 8).

When iterating over these binary digits backwards, 1 means the corresponding power of base is multiplied to

the final result, and 0 means not.

 1     # @param {float} x
 2     # @param {integer} n
 3     # @return {float}
 4     def myPow(self, x, n):
 5         pz=1
 6         if n<0:
 7             pz=-1
 8             n=abs(n)
 9         r=1
10         base=x
11         while n!=0:
12             if n%2==1:
13                 r*=base
14             base*=base
15             n/=2
16         return r if pz==1 else 1.0/r

Note that the sign of n should be handled.