> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/mathematics/powx-n.md).

# Pow(x, n)

Implement [pow(*x*,*n*)](http://www.cplusplus.com/reference/valarray/pow/), which calculates *x\_raised to the power\_n* (x^n).

**Example 1:**

```
Input:
 2.00000, 10

Output:
 1024.00000
```

**Example 2:**

```
Input:
 2.10000, 3

Output:
 9.26100
```

**Example 3:**

```
Input:
 2.00000, -2

Output:
 0.25000

Explanation:
 2
-2
 = 1/2
2
 = 1/4 = 0.25
```

**Note:**

* **-100.0 < x < 100.0**
* **n is a 32-bit signed integer, within the range \[−2^31, 2^31 − 1]**

## Analysis

有几点需要注意：

1. n是有符号的，因此在循环之前，最好统一转化为正整数，如果n是负数，则x变成 1/x，n = -n 即可
2. 由于n取值范围`[−2^31, 2^31 − 1]` 因此，最好先用长整型long来存n，再转换符号，否则有可能溢出 (To handle the case where N=Interger.MIN\_VALUE we use a long (64-bit) variable)

单纯地循环相乘n次之外，更快的方式是fast power，基本思想就是

`n = ∑ [(2^i)]`

因此 `x^n = x^ {∑ [(2^i)]}`

`x^[2^(i-1)] * x^[2^(i-1)] -> x^[2^i]`

例如

`x^17 = x^(2^4) * x^(2^0)`

`x^9 = x^(2^3) * x^(2^0)`

`x^5 = x^(2^2) * x^(2^0)`

**Algorithm:**

![](/files/-M63nVN9y9gjsYqzZPW7)

## Solution

### Fast Power Iterative - O(logn) time

Note using `long N` for `N = -N` to avoid overflow.

```java
class Solution {
    public double myPow(double x, int n) {
        long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        double ans = 1;
        double current_product = x;
        for (long i = N; i > 0; i /= 2) {
            if ((i % 2) == 1) {
                ans = ans * current_product;
            }
            current_product = current_product * current_product;
        }
        return ans;
    }
}
```

### **Fast Power Recursive** - O(logn) time - (8 ms, faster than 83.96%)

```java
class Solution {

    double myPow(double x, int n){

        if (n == 0) {
            return 1.0;
        } else {  
            double half = myPow(x, n / 2);
            if (n % 2 == 0){
                return half * half;
            } else {
                if (n > 0){
                    return half * half * x;
                } else {
                    return half * half / x;
                }                
            }   
        }
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/mathematics/powx-n.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.