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


  • 1
    L
    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;
        }
    

  • 1
    J

    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;
        }
    };
    
    

  • 0
    L

    @j20120307 Great solution


Log in to reply
 

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