8ms JAVA solution using fast power


  • 8
    F
    private static final int M = 1337;
    
        public int normalPow(int a, int b) {
            int result = 1;
            while (b != 0) {
                if (b % 2 != 0)
                    result = result * a % M;
                a = a * a % M;
                b /= 2;
            }
            return result;
        }
    
        public int superPow(int a, int[] b) {
            a %= M;
            int result = 1;
            for (int i = b.length - 1; i >= 0; i--) {
                result = result * normalPow(a, b[i]) % M;
                a = normalPow(a, 10);
            }
            return result;
        }
    

  • 0

    I convert b to a number first and then use bit manipulation to solve it. It's clear and concise. The number in the operations will never be larger than 1337.

        def superPow(self, a, b):
            b = int(''.join(map(str, b)))
            res = 1
            a %= 1337
            cache = a
            while b > 0:
                if b & 1:
                    res = (res * cache) % 1337
                cache = (cache ** 2) % 1337
                b >>= 1
            return res
    

Log in to reply
 

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