# Go4Fun - Functional programming and more # Rust Interview Puzzles: Raise a number to a power

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

Rust Playground with this code