10ms O(b.length) java solution with math explained


  • 0
    E
    public class Solution {
        public int superPow(int a, int[] b) {
            if(b==null || b.length==0) return 0;
            
            int len = b.length;
            
            /* the remainders for each digit of b
            for example: given b = [1,0], remainder[0] = a^(10)%1337
            */
            int[] remainders = new int[len];
            int first = a % 1337;
            for(int i=len-1; i>=0; i--) {
                //the remainders for 0-9 in digit i
                int[] nums = new int[11];
                nums[0] = 1;
                for(int j=1; j<11; j++) {
                    nums[j] = (nums[j-1]*first) % 1337;
                }
                
                remainders[i] = nums[b[i]];
                // the remainder for 10 is the remainder for 1 in the next digit
                first = nums[10];
            }
            
            //calculate the final remainder using the remainders for each digit
            int remainder = 1;
            for(int i=0; i<len; i++) {
                remainder = (remainder*remainders[i]) % 1337;
            }
            
            return remainder;
        }
    }
    

Log in to reply
 

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