Python more general solution - deal with case where e.g. b = [123, 58, 2, 13]...


  • 0
    A
    class Solution(object):
        def superPow(self, a, b):
            """
            :type a: int
            :type b: List[int]
            :rtype: int
            """
            a %= 1337
            if a == 0:
                return 0
            a_mods, a_cnt, tmp = [a], 1, a**2 % 1337
            while tmp != a:
                a_mods.append(tmp)
                tmp = tmp * a % 1337
                a_cnt += 1
            t_start = 10 % a_cnt
            t_mods, t_cnt, tmp = [t_start], 1, t_start**2 % a_cnt
            while tmp != t_start:
                t_mods.append(tmp)
                tmp = tmp * t_start % a_cnt
                t_cnt += 1
            # get final modulus 
            final_mod, digits = a_mods[(b[-1]-1) % a_cnt] if b[-1] != 0 else 1, len(str(b[-1]))
            for i in range(len(b)-2, -1, -1):
                final_mod = final_mod * a_mods[(b[i] % a_cnt * t_mods[(digits-1) % t_cnt]-1) % a_cnt] % 1337
                digits += len(str(b[i]))
            return final_mod
    

Log in to reply
 

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