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:

## 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.

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.

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

Recursive Version:

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

Comment Junhao Wang
Hi, I was a master student at USC studying Computer Science.