Leetcode: strStr - SUNDAY algorithm

more >>

Leetcode: Pow(X,n)

Naive thinking is just multiple X for n times, but this is absolutely not this question wants.

We need to make use of the calculation result in previous steps, since X^n = X^n/2 * X^n/2

What if n is odd? Then we need to multiple X one more times.

1
2
3
4
5
6
7
8
9
10
11

public class Solution {
    public double pow(double x, int n) {
      double result = 1.0;
      for(int i = n; i != 0; i /= 2, x *= x) {
          if( i % 2 != 0 ) {
              result *= x;
          }
      }
      return n < 0 ? 1.0 / result : result;
    }
}