How do I solve the Double Modular Exponentiation problem?

You solve it by iterating over each set of variables, calculating the modular exponentiation for each, and checking if the result matches the target.

What is modular exponentiation?

Modular exponentiation is the process of raising a number to a power and then taking the remainder when divided by a modulus.

How can I optimize my solution for large numbers in this problem?

You can use fast exponentiation (also known as exponentiation by squaring) to handle large exponents efficiently without directly calculating the full power.

What happens if no indices are good in Double Modular Exponentiation?

If no indices are good, the solution should return an empty array, indicating that none of the rows met the condition.

Why is the time complexity O(n) for this problem?

The time complexity is O(n) because we only iterate over each row of the 2D array once, and each modular exponentiation operation is constant-time.

#2961

Medium

auto_awesome数组·数学

LeetCode 题解工作台

双模幂运算

给你一个下标从 0 开始的二维数组 variables ，其中 variables[i] = [a i , b i , c i, m i ] ，以及一个整数 target 。如果满足以下公式，则下标 i 是好下标： 0 ((a i b i % 10) c i ) % m i == target…

数组数学模拟

题目描述

给你一个下标从 0 开始的二维数组 variables ，其中 variables[i] = [a_i, b_i, c_i, m_i]，以及一个整数 target 。

如果满足以下公式，则下标 i 是 好下标：

0 <= i < variables.length
((a_i^b_i % 10)^c_i) % m_i == target

返回一个由 好下标 组成的数组，顺序不限 。

示例 1：

输入：variables = [[2,3,3,10],[3,3,3,1],[6,1,1,4]], target = 2
输出：[0,2]
解释：对于 variables 数组中的每个下标 i ：
1) 对于下标 0 ，variables[0] = [2,3,3,10] ，(2³ % 10)³ % 10 = 2 。
2) 对于下标 1 ，variables[1] = [3,3,3,1] ，(3³ % 10)³ % 1 = 0 。
3) 对于下标 2 ，variables[2] = [6,1,1,4] ，(6¹ % 10)¹ % 4 = 2 。
因此，返回 [0,2] 作为答案。

示例 2：

输入：variables = [[39,3,1000,1000]], target = 17
输出：[]
解释：对于 variables 数组中的每个下标 i ：
1) 对于下标 0 ，variables[0] = [39,3,1000,1000] ，(39³ % 10)¹⁰⁰⁰ % 1000 = 1 。
因此，返回 [] 作为答案。

提示：

1 <= variables.length <= 100
variables[i] == [a_i, b_i, c_i, m_i]
1 <= a_i, b_i, c_i, m_i <= 10³
0 <= target <= 10³

lightbulb

解题思路

方法一：模拟 + 快速幂

我们直接根据题目描述模拟即可。对于幂运算取模，我们可以使用快速幂来加速运算。

时间复杂度 $O(n \times \log M)$ ，其中 $n$ 为数组 $variables$ 的长度；而 $M$ 为 $b_i$ 和 $c_i$ 中的最大值，本题中 $M \le 10^3$ 。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

class Solution:
    def getGoodIndices(self, variables: List[List[int]], target: int) -> List[int]:
        return [
            i
            for i, (a, b, c, m) in enumerate(variables)
            if pow(pow(a, b, 10), c, m) == target
        ]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate should be able to break down the modular arithmetic into clear steps and explain how modular exponentiation works.
question_mark
A good approach will involve optimizing the power calculations using efficient algorithms such as fast exponentiation.
question_mark
Look for a solution that correctly handles edge cases, such as large values of `ai`, `bi`, and `mi`.

warning

常见陷阱

外企场景

error
Candidates may fail to correctly apply modular arithmetic or overlook the second modulo operation, which could lead to incorrect results.
error
Some candidates might use brute-force exponentiation, which can be inefficient for large values of `bi`.
error
Incorrectly handling edge cases like when `target` is 0 or when the `variables` array has fewer than expected elements could lead to errors.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Increase the size of the array and test the algorithm's scalability with higher values of `ai`, `bi`, `ci`, and `mi`.
arrow_right_alt
Test cases where the `target` is much smaller or larger than the computed results to check if the solution handles a wide range of values.
arrow_right_alt
Test cases where all indices are good or none are good, to see if the solution properly handles these extremes.

help

常见问题

外企场景

继续练习

#2946 循环移位后的矩阵相似检查 #3179 K 秒后第 N 个元素的值 #3264 K 次乘运算后的最终数组 I