Reference: LeetCode

Difficulty: Medium

## Problem

Implement

`pow(x, n)`

, which calculates $x$ raised to the power $n$ ($x^n$).

**Note:**

- $-100.0 < x < 100.0$
- $n$ is a 32-bit signed integer, within the range $[-2^{32}, 2^{32}]$

**Example:**

1 | Input: 2.00000, 10 |

## Analysis

### Brute-Force

Simulate the process, multiply `x`

for `n`

times.

**Note:**

- Consider the case
`n < 0`

and`n == 0`

- Use
`long N`

to handle the case`n = -2147483648`

.

1 | public double myPow(double x, int n) { |

**Time:** $O(N)$**Space:** $O(1)$

### Binary Representation

Since there is $x^{a + b} = x^a \times x^b$, we can process $n$ in binary representation. For example, $x^{52} = x^{110100} = x^{100000} \times x^{010000} \times x^{100}$, so we just need to figure out each of these three terms and calculate the product of them.

`p`

starts from $1 (0000001)$ to $32 (1000000)$. Each time we left shift`p`

by one bit.- In correspondence with
`p`

, we have`currProd`

to store values of $x^{0000001}$, $x^{0000010}$, …, $x^{1000000}$. - If the bit is on, we accumulate
`currProd`

to`result`

.

**Note:**

- Use
`long N`

to handle the case`n = -2147483648`

. - The condition of
`while`

is`p <= N`

.

1 | public double myPow(double x, int n) { |

**Time:** $O(\log{N})$ equal to the number of bits required to represent $N$.**Space:** $O(1)$

**Recursive Version:**

1 | public double myPow(double x, int n) { |

**Time:** $O(\log{N})$**Space:** $O(\log{N})$