### Problem

Given 2 integer numbers, `b`

and a non-negative `n`

, we need to raise the number `b`

to the power of `n`

.

#### Examples:

Input `b` | Input `n` | Output |

`2` | `4` | `16` |

`-2` | `3` | `-8` |

`-2` | `10` | `1024` |

`5` | `0` | `1` |

### Solution

```
fn pow(mut b: i32, mut n: u32) -> i32 {
let mut pow: i32 = 1;
while n > 0 {
if (n % 2) == 1 {
pow *= b;
}
n /= 2;
b *= b;
}
pow
}
```

### Explanation

A naive one-liner solution could be just to iterate `n`

times and multiply `b`

:

```
fn pow(b: i32, n: u32) -> i32 {
(0..n).fold(1, |acc, _| acc * b)
}
```

It would work but would have the linear time complexity `O(n)`

which is not ideal. Instead, the Solution has the time complexity `O(log n)`

.

The idea of the Solution is to divide the number `n`

by `2`

and multiply `b`

to itself `while n > 0`

. This way instead of multiplying `b`

`n`

times one by one, we are taking an "exponential shortcut", so to speak. In other words, instead of doing e.g. `3*3*3*3*3*3*3*3`

like in the naive solution, we do `((3^2)^2)^2`

.

One tricky part here is that we need to add special handling for situations when `n`

becomes an odd number `(n % 2) == 1`

. In essence, that is needed to process cases when the current power of `n`

is not divisible by `2`

like in `3^5`

. In this case, we need an additional multiplication like `((3^2)^2)*3`

.

### Complexity

The time complexity of the solution is `O(log n)`

(where `n`

is the power we need to raise the number to).