# Java Solution using stack inspired by Pow(x,n)

• ``````public static final int M = 1337;
public int superPow(int a, int[] b) {
Stack<Integer> stack = new Stack();
for(int digit: b) stack.push(digit);
return myPow(a, stack);
}

public int myPow(int a, Stack<Integer> stack){
if(stack.isEmpty()) return 1;
int last = stack.pop();
return fastPow(myPow(a, stack), 10) * fastPow(a, last) % M;
}

// calculate a^k % M
public int fastPow(int a, int k){
if(k == 0) return 1;
a %= M;
if((k&1) == 1) return a * fastPow(a*a, k/2)%M;
else return fastPow(a*a, k/2)%M;
}
``````

• Same algorithm in C++:

``````
class Solution {
public:
int superPow(int a, vector<int> b) {
stack<int> s;
for (int& digit: b) s.push(digit);
return myPow(a, s);
}
private:
const int M = 1337;
// calculate a^k % M
int fastPow(int a, int k) {
if (k == 0) return 1;
a %= M;
if (k&1) return a*fastPow(a*a, k/2) % M;
else return fastPow(a*a, k/2) % M;
}

int myPow(int a, stack<int>& s) {
if (s.empty()) return 1;
int last = s.top();
s.pop();
return fastPow(myPow(a, s), 10) * fastPow(a, last) % M;
}
};

``````

• @j20120307 Great solution

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.