What is the most efficient way to compute Super Pow for very large b arrays?

Use modular exponentiation with divide-and-conquer, recursively splitting b and applying modulo 1337 at each step.

Why can't I directly compute a^b in Super Pow?

Because b can be extremely large, direct computation will overflow typical integer types and is impractical.

How do I handle b represented as an array of digits?

Split b into prefix and last digit recursively, compute each partial power modulo 1337, then combine results.

What edge cases should I consider in Super Pow?

Check for a = 1, b = [0], or any leading zeros in b, ensuring all modular steps are applied correctly.

Can GhostInterview show intermediate steps for debugging Super Pow?

Yes, it breaks down recursive calls and modular multiplications, helping trace how final results are computed safely.

#372

Medium

auto_awesome数学·结合·divide·conquer

LeetCode 题解工作台

超级次方

你的任务是计算 a b 对 1337 取模， a 是一个正整数， b 是一个非常大的正整数且会以数组形式给出。示例 1：输入： a = 2, b = [3] 输出： 8 示例 2：输入： a = 2, b = [1,0] 输出： 1024 示例 3：输入： a = 1, b = [4,3,3…

数学分治

题目描述

你的任务是计算 a^b 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。

示例 1：

输入：a = 2, b = [3]
输出：8

示例 2：

输入：a = 2, b = [1,0]
输出：1024

示例 3：

输入：a = 1, b = [4,3,3,8,5,2]
输出：1

示例 4：

输入：a = 2147483647, b = [2,0,0]
输出：1198

提示：

1 <= a <= 2³¹ - 1
1 <= b.length <= 2000
0 <= b[i] <= 9
b 不含前导 0

lightbulb

解题思路

方法一：快速幂

我们初始化答案变量 $ans = 1$ 。

接下来，倒序遍历数组 $b$ ，每次遍历到一个元素 $e$ ，我们将答案变量 $ans$ 自乘 $a^e$ 并对 $1337$ 取模，然后将 $a$ 自乘 $10$ 次并对 $1337$ 取模。这里需要用到快速幂。

遍历完数组后，返回答案即可。

时间复杂度 $O(\sum_{i=0}^{n-1} \log b_i)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        mod = 1337
        ans = 1
        for e in b[::-1]:
            ans = ans * pow(a, e, mod) % mod
            a = pow(a, 10, mod)
        return ans

speed

复杂度分析

指标	值
时间	complexity depends on the length of b; each recursive step reduces b by one digit, and modular exponentiation takes constant time per step, yielding roughly O(n log a) time. Space complexity is O(n) due to recursion stack proportional to b's length.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect you to recognize that direct exponentiation will overflow for large b arrays.
question_mark
Interviewers want to see divide-and-conquer applied to array-based exponentiation with modulo optimization.
question_mark
Clarifying edge cases for a = 1 or b = [0] can demonstrate thorough understanding.

warning

常见陷阱

外企场景

error
Attempting direct calculation of a^b without modular reduction causes overflow.
error
Ignoring the array nature of b leads to miscalculating large exponents.
error
Forgetting to apply modulo 1337 at each step produces incorrect results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute a^b mod m for different modulus values, adjusting recursive multiplication accordingly.
arrow_right_alt
Handle exponents given in string format rather than array digits.
arrow_right_alt
Support negative base values with proper modular handling.

help

常见问题

外企场景

继续练习

#932 漂亮数组 #973 最接近原点的 K 个点 #371 两整数之和