Given a, n, calculate a^n in non-recursive way.

The traditional way is to use recursion to reach O(logN) solution. For iteration, we can use stack to implement the recursion process. In stack, 1 means result times a, -1 means result times result, 0 doing nothing.

Take 11 as example, the process is like:

Take 15 as example, the process is like:

Below is my code:

public static intpower(inta,intn) {// build stackStack s =newStack(); s.add(n);while(s.peek()>1) {intcurr = s.pop(); s.push(curr%2);//1 means result should time a.s.push(-1);//-1 means result should time result.s.push(curr/2); }intresult = 1;while(!s.isEmpty()) {intcurr = s.pop();switch(curr) {case1: result = result * a;break;case-1: result = result * result;break; } }returnresult; }

However, this problem can be solved in O(logN) time and O(1) space. Below is a process to calculate a^9:

public static intpower(inta,intn) {intresult = 1;while(n>0) {if(n%2==1) result = result * a; a = a * a; n = n>>1; }returnresult; }

In order to understand this solution more clearly, we can transform the exponent in binary: . We know **a** in the code is a base. It changes like: . And we know . In this way, we know that calculating is similar the process to build binary **1001**. The difference is that instead doing plus, we do multiplication.

In the code, **a = a* a** is to enlarge the base. **result = result * a** is to add the base in the result.

Pingback: Super Power | allenlipeng47()