Java solution


  • 1
    A

    Here I use the formula:

    ab mod m = ( (a mod m) * ( b mod m) ) mod m;

    So the following formula would be achieved:
    mod = ( (pow(mod,10) % 1377) * (pow(a,b[i])) % 1377) ) % 1377;
    i is the current index of b, mod is the modular by (i-1);

    However, both of pow(mod,10) and pow(a,b[i]) are potential to exceed the maximum of integer, so here two while loops are used to calculate the value of (pow(mod,10) % 1377) and (pow(a,b[i])) % 1377).

    My code:

    public class Solution { 
       public int superPow(int a, int[] b) {        
            final int M = 1337;
           
            int mod = 1; int curr =  a; int pow = 0; int j = 0;
            int mod_temp, mod_curr; 
            
            for (int i = 0; i < b.length; i++){
                
                 j = 0;
                /* calculate the mod of previous mod ^ 10  */ 
                mod_temp = 1; 
                while(j++ < 10){
                    mod_temp = (mod_temp * mod) % M;
                }
                
               j = 0; 
               mod_curr = 1;
                /* calculate the mod of a ^ b[i] */
                while(j++ < b[i]){
                    mod_curr = (mod_curr * (a%M)) % M;   
                }
                
                mod = (mod_temp * mod_curr) % M;
                
            }
            
            return mod;
        }
    }
    
    

Log in to reply
 

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