By Long Luo

We know how to find $$2.0$$ raised to the power $$10$$. The easiest way is to multiply $$10$$ times $$2.0$$ by loop, but what if we have to find $$2.0$$ raised to the power very large number such as $$10000$$ or more?

We will discuss how to find the solution of such problems by using an fast, efficient algorithm.

# Brute Force

We multiply $$a$$ to itself $$b$$ times. That is, $$a^b = \underbrace{a \times a \dots \times a}_b$$.

A simple java implementation of that would be:

## Analysis

• Time Complexity: $$O(n)$$
• Space Complexity: $$O(1)$$

# Exponentiation by Squaring

Exponentiation by Squaring can help us in finding the powers of large positive integers. The key is to the divide the power in half at each step.

The following recursive approach expresses the same idea:

$a^n = \begin{cases} 1 &\text{if } n == 0 \\ \left(a^{\frac{n}{2}}\right)^2 &\text{if } n > 0 \text{ and } n \text{ even} \\ \left(a^{\frac{n - 1}{2}}\right)^2 \cdot a &\text{if } n > 0 \text{ and } n \text{ odd} \\ \end{cases}$

Let’s take an example:

$3^{10} = 3 \times 3 \times 3 \times 3 \times 3 \times 3 \times 3 \times 3 \times 3 \times 3$

Try to divide the power by $$2$$:

$3^{10} = (3 \times 3) \times (3 \times 3) \times (3 \times 3) \times (3 \times 3) \times (3 \times 3)$

$3^{10} = ((3 \times 3) ^ 5)$

$3^{10} = 9^5$

Effectively, power is divided by $$2$$ and base is multiplied to itself. So we can write $$3^10 = 9^5$$.

Now, our problem is to find $$9^5$$.

$9^5 = 9 \times 9 \times 9 \times 9 \times 9$

// Try to divide the power by $$2$$ // Since the power is an odd number here, we cannot do so. // However there’s another way to represent $$9^5$$

$9^5 = (9^4) \times 9$

// Now we can find $$9^4$$ and later multiple the extra $$9$$ to the result

$9^5 = (81^2) \times 9$

Effectively, when power is not divisible by $$2$$, we make power even by taking out the extra $$9$$. Then we already know the solution when power is divisible by $$2$$. Divide the power by $$2$$ and multiply the base to itself.

Now our problem is to find $$(81^2) \times 9$$

$(81^2) \times 9 = (81 \times 81) \times 9$

// Try to divide the power by $$2$$ $(81 ^ 2) \times 9 = (6561 ^ 1) \times 9$

Finally, we have our solution $$3^10 = (6561^1) \times 9 = 6561 \times 9 = 59049$$

Let’s use recusive in java.

## Analysis

• Time Complexity: $$O(\log n)$$
• Space Complexity: $$O(\log n)$$

# Iterative

Although the complexity of both approaches is identical, but if we use iteration instead of recursion will be faster in practice since we don’t have the overhead of the recursive calls and reduce the space.

## Analysis

• Time Complexity: $$O(logn)$$
• Space Complexity: $$O(logn)$$

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗