There is a leetcode problem Pow(x, n). Basically, it is a plain power function.

We can follow the description and multiple number x with n times.

```
function myPow(x: number, n: number): number {
// for negative n, we need to do a 1/x operation
if (n < 0) {
n = -1 * n;
x = 1 / x;
}
let ans = 1;
for (let i = 0; i < n; i++) {
ans *= x;
}
return ans;
};
```

As you can see, in this way, the time complexity is `O(n)`

.

We can use a divide and conquer approach to make the time complexity `O(log(n))`

.

The idea behind this algorithm is based on the ideas below.

If number n is even, then we can have:

```
x^n = x^(n/2) * x^(n/2)
```

So with this idea, we can calculate `x^n`

with only `n/2+1`

multiplication operations, instead of `n`

times. (Suppose we do `x^(n/2)`

with the brute-force approach).

If number n is odd, we can just minus 1 to make it even:

```
n = n - 1
x^n = x^(n/2) * x^(n/2) * x
```

So with this simple idea, let's see it in code.

```
function myPow(x: number, n: number): number {
if (n < 0) {
n = -1 * n;
x = 1 / x;
}
if (n === 0) return 1;
if (n % 2 === 0) {
const v = myPow(x, n / 2);
return v * v;
} else {
const v = myPow(x, (n-1) / 2);
return v * v * x;
}
};
```