# power(a, n) in iteration way

By | November 28, 2015
Share the joy
•
•
•
•
•
•

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 int power(int a, int n) {
// build stack
Stack s = new Stack();
while(s.peek()>1) {
int curr = 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);
}
int result = 1;
while(!s.isEmpty()) {
int curr = s.pop();
switch (curr) {
case 1:
result = result * a;
break;
case -1:
result = result * result;
break;
}
}
return result;
}```

However, this problem can be solved in O(logN) time and O(1) space. Below is a process to calculate a^9: ```public static int power(int a, int n) {
int result = 1;
while(n>0) {
if(n%2==1)
result = result * a;
a = a * a;
n = n>>1;
}
return result;
}```

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.