Problem

Given 2 integer numbers, b and a non-negative n, we need to raise the number b to the power of n.

Examples:

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