My easy understood JAVA solution with explanation. Any idea how to make it faster?


  • 2

    My idea is to split the number we have into two parts: repeater and remainder.
    For example:
    2^40 :
    1. First we construct the smallest repeater which is >= 1337.
    Coz 2^10 < 1337 < 2^11, we choose 2^11 as repeater.
    2. Then we have 2^30: 2^11, 2^11, 2^11 and 2^8, 2^8 is the remainder that is smaller than repeater.
    3. We do the mod with 1337 : 711, 711, 711, 2^8
    4. Repeat Step 1, combine the rest part of repeater with the remainder and do mod:
    (711^2, (711*2^8) mod 1337)

    1. Do the repeat process until we get for a^b, a==1 or b<=1;

    Code:

    import java.math.BigInteger;
    
    public class Solution {
        public int superPow(int a, int[] b) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < b.length; i++){
                sb.append(b[i]);
            }
            BigInteger numB = new BigInteger(sb.toString());
            return helper((long)a, numB, 1);
            
        }
        public int helper(long a, BigInteger b, long remainder){
            if (a == 1 || (b.compareTo(BigInteger.valueOf(1)) <= 0)) 
                return (int)(((a % 1337)*(remainder % 1337)) % 1337);
            
            BigInteger powNeed = BigInteger.valueOf((long)(Math.log(1337)/Math.log(a)) + 1);
            long newA = (b.compareTo(powNeed) < 0) ? 1 : (long)(Math.pow(a,powNeed.intValue()) % 1337);
            long newRemainder = (long)(((remainder % 1337)*(Math.pow(a, b.mod(powNeed).intValue()) % 1337)) % 1337);
            return helper(newA, b.divide(powNeed), newRemainder);
        }
    }
    

Log in to reply
 

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