Java 16 lines AC solution 11ms


  • 4
    H

    just a java version
    you can check the C++ solution with more detail here
    Basic math knowlege:
    (ab)%k=(a%k)(b%k)%k;
    (abc)%k=(a%k)(b%k)(c%k)%k

    An example:

    23^1335%base
    =(23^1330%base)(23^5%base)%base
    =((23^133%base)^10)%base
    (23^5%base)%base
    =function(function(23,133),10)*function(23,5)%base

    public class Solution {
        int base =1337;
        public int superPow(int a, int[] b) {
            return helper(a,b,b.length-1);
        }
        int helper(int a,int[]b,int endidx){
            if(endidx==-1) return 1;
            int last_digit=b[endidx];
            return powmod(helper(a,b,endidx-1),10)*powmod(a,last_digit)%base;
        }
        int powmod(int a,int k){
            a%=base;
            int result=1;
            for(int i=0;i<k;i++){
                result=(result*a)%base;
            }
            return result;
        }
    }
    

Log in to reply
 

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