Java O(n) solution


  • 0
    M

    Time: O(n), where n=b.length

    public class Solution {
        private static final int BASE = 1337;
        public int superPow(int a, int[] b) {
        	if(a==0 || a==1) return a;
            return superPowMod(a, b, b.length-1);
        }
        //O(n), where n=b.length
        private int superPowMod(int a, int[] b, int index){
            if(index<0) return 1;
            int c = superPowMod(a, b, index-1);
            return (powMod(c, 10) * powMod(a, b[index])) % BASE;
        }
        //O(10)
        private int powMod(int a, int m){
            if(a==1) return 1;
            int res = 1;
            int pow = a%BASE;
            for(int i=0; i<m; i++){
                res = (res*pow)%BASE;
            }
            return res;
        }
    }
    

Log in to reply
 

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