*x*,

*n*).

**Understand the problem:**

This problem looks quite simple at the first glance, however requires considering many corner cases. As defined in the interface, x is a double type, n is int, the return is double.

Consider when n is negative.

**Naive Solution:**

A very straight-forward idea is noticing that x^n equals to x * x * x... x, so we just need to time them up.

**Code (Java):**

public class Solution { public double pow(double x, int n) { double result = 1; for (int i = 0; i < n; i++) { result *= x; } return result; } }

**Discussion:**

The solution has time complexity O(n). It got the TLE error on OJ. Thus we need to figure out a more efficient solution.

**A better solution:**

We can do it in O(logn) time, think about the reduction operations in logn time. We can do it similar. We can use a recursive solution:

**Code (Java):**

public class Solution { public double pow(double x, int n) { if (n < 0) { return 1 / powHelper(x, -n); } else { return powHelper(x, n); } } private double powHelper(double x, int n) { if (n == 0) return 1; double v = powHelper(x, n/2); if (n % 2 == 0) { return v * v; } else { return v * v * x; } } }

**Summary:**

This problem is not hard naturally, but the O(logn) solution requires a bit more effort. Do consider recursion when you are found you can divide the problem into smaller problems.

## No comments:

## Post a Comment