# LeetCode 50: Pow(x, n)

## Problem Restatement

We need to implement `pow(x, n)`.

Given a floating-point number `x` and an integer `n`, return `x` raised to the power `n`.

The official problem asks us to calculate `x` raised to `n`, written as `x^n`. Example inputs include `x = 2.00000, n = 10`, which returns `1024.00000`, and `x = 2.00000, n = -2`, which returns `0.25000`.

For a negative exponent:

```python
x ** -n = 1 / (x ** n)
```

For example:

```python
2^-2 = 1 / 2^2 = 1 / 4 = 0.25
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | A float `x` and an integer `n` |
| Output | The value of `x` raised to the power `n` |
| Negative exponent | Return the reciprocal of the positive power |
| Goal | Compute efficiently without multiplying `x` one step at a time |

Function shape:

```python
def myPow(x: float, n: int) -> float:
    ...
```

## First Thought: Multiply Repeatedly

The simplest idea is to multiply `x` by itself `n` times.

For example:

```python
x = 2
n = 10
```

We could compute:

```python
2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2
```

This gives:

```python
1024
```

Code for positive `n`:

```python
result = 1.0

for _ in range(n):
    result *= x
```

This works for small `n`, but it is too slow when `n` is large.

LeetCode allows `n` to be as small as `-2^31` and as large as `2^31 - 1`, so an `O(n)` loop is not acceptable for large exponents.

## Key Insight

Use binary exponentiation.

Instead of multiplying one copy of `x` at a time, repeatedly square the base.

For example:

```python
x^10 = x^8 * x^2
```

We can get these powers by squaring:

```python
x
x^2
x^4
x^8
```

The exponent `10` in binary is:

```python
1010
```

That means:

```python
10 = 8 + 2
```

So:

```python
x^10 = x^8 * x^2
```

Binary exponentiation uses the bits of `n` to decide which powers of `x` should be multiplied into the answer.

## Algorithm

First handle negative exponents.

If `n < 0`, change the problem from:

```python
x^n
```

to:

```python
1 / x^(-n)
```

Then compute the positive exponent using a loop.

Initialize:

```python
result = 1.0
base = x
exp = abs(n)
```

While `exp > 0`:

1. If `exp` is odd, multiply `result` by `base`.
2. Square `base`.
3. Divide `exp` by `2` using integer division.

At the end, if the original exponent was negative, return `1 / result`.

Otherwise, return `result`.

## Walkthrough

Use:

```python
x = 2
n = 10
```

Start:

```python
result = 1
base = 2
exp = 10
```

Since `10` is even, do not multiply `result`.

Square the base:

```python
base = 4
exp = 5
```

Now `5` is odd, so multiply:

```python
result = 1 * 4 = 4
```

Square again:

```python
base = 16
exp = 2
```

`2` is even, so do not multiply.

Square again:

```python
base = 256
exp = 1
```

`1` is odd, so multiply:

```python
result = 4 * 256 = 1024
```

Now:

```python
exp = 0
```

Return:

```python
1024
```

## Correctness

The algorithm keeps `result` as the product of the powers of `x` selected from the binary representation of the exponent.

At each step, `base` represents the current power of `x`.

Initially, `base = x`, which corresponds to `x^1`.

After one squaring, `base = x^2`.

After another squaring, `base = x^4`.

Then `x^8`, `x^16`, and so on.

When the current exponent bit is `1`, that power is part of the final answer, so the algorithm multiplies it into `result`.

When the bit is `0`, that power is skipped.

Integer-dividing the exponent by `2` moves to the next binary bit.

Therefore, after all bits have been processed, `result` equals `x^abs(n)`.

If `n` was negative, the mathematical definition gives:

```python
x^n = 1 / x^(-n)
```

So returning the reciprocal gives the correct value.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(log |n|)` | The exponent is divided by `2` each iteration |
| Space | `O(1)` | Only a few variables are used |

## Implementation

```python
class Solution:
    def myPow(self, x: float, n: int) -> float:
        exp = abs(n)
        base = x
        result = 1.0

        while exp > 0:
            if exp % 2 == 1:
                result *= base

            base *= base
            exp //= 2

        if n < 0:
            return 1.0 / result

        return result
```

## Code Explanation

We convert the exponent to a non-negative value:

```python
exp = abs(n)
```

In Python, this is safe for very small negative integers because Python integers do not overflow.

We keep the current power in:

```python
base = x
```

The result starts at `1.0` because multiplying by `1` does not change the answer:

```python
result = 1.0
```

The loop processes the exponent bit by bit:

```python
while exp > 0:
```

If the current exponent is odd, its lowest binary bit is `1`, so we include the current base:

```python
if exp % 2 == 1:
    result *= base
```

Then we square the base:

```python
base *= base
```

This moves from `x`, to `x^2`, to `x^4`, to `x^8`.

Then we discard the lowest bit:

```python
exp //= 2
```

Finally, if the original exponent was negative, return the reciprocal:

```python
if n < 0:
    return 1.0 / result
```

Otherwise, return the computed positive power.

## Testing

```python
def almost_equal(a, b, eps=1e-9):
    return abs(a - b) < eps

def run_tests():
    s = Solution()

    assert almost_equal(s.myPow(2.0, 10), 1024.0)
    assert almost_equal(s.myPow(2.1, 3), 9.261)
    assert almost_equal(s.myPow(2.0, -2), 0.25)
    assert almost_equal(s.myPow(1.0, -2147483648), 1.0)
    assert almost_equal(s.myPow(-2.0, 3), -8.0)
    assert almost_equal(s.myPow(-2.0, 4), 16.0)
    assert almost_equal(s.myPow(5.0, 0), 1.0)

    print("all tests passed")

run_tests()
```

| Test | Expected | Reason |
|---|---:|---|
| `2.0, 10` | `1024.0` | Standard positive exponent |
| `2.1, 3` | `9.261` | Floating-point base |
| `2.0, -2` | `0.25` | Negative exponent |
| `1.0, -2147483648` | `1.0` | Very small exponent |
| `-2.0, 3` | `-8.0` | Negative base with odd exponent |
| `-2.0, 4` | `16.0` | Negative base with even exponent |
| `5.0, 0` | `1.0` | Any nonzero base to power zero |