#2961

Medium

LeetCode Problem Workspace

Double Modular Exponentiation

Solve the Double Modular Exponentiation problem by applying array manipulation and modular arithmetic to find good indices.

array math simulation

Problem Statement

You are given a 2D array variables where each row variables[i] consists of four integers [ai, bi, ci, mi]. You also receive an integer target. The goal is to compute a value using the formula ((ai^bi) % mi) % ci. For each index i, if the result equals target, then index i is considered a 'good' index.

Return an array containing all the indices that satisfy this condition. Indices can be returned in any order.

Examples

Example 1

Input: variables = [[2,3,3,10],[3,3,3,1],[6,1,1,4]], target = 2

Output: [0,2]

For each index i in the variables array:

For the index 0, variables[0] = [2,3,3,10], (23 % 10)3 % 10 = 2.
For the index 1, variables[1] = [3,3,3,1], (33 % 10)3 % 1 = 0.
For the index 2, variables[2] = [6,1,1,4], (61 % 10)1 % 4 = 2. Therefore we return [0,2] as the answer.

Example 2

Input: variables = [[39,3,1000,1000]], target = 17

Output: []

For each index i in the variables array:

For the index 0, variables[0] = [39,3,1000,1000], (393 % 10)1000 % 1000 = 1. Therefore we return [] as the answer.

Constraints

1 <= variables.length <= 100
variables[i] == [ai, bi, ci, mi]
1 <= ai, bi, ci, mi <= 103
0 <= target <= 103

Solution Approach

Modular Exponentiation

For each index i, calculate the modular exponentiation of ai^bi % mi and then apply the second modulo operation % ci. This ensures we are performing the modular arithmetic exactly as required.

Iterating Over the 2D Array

Iterate through each row of the variables array, applying the modular exponentiation formula for each set of values. If the result matches the target, add the index to the result array.

Handling Large Numbers

Given the constraints where ai, bi, ci, and mi can be as large as 1000, make sure to efficiently handle large values by using the properties of modular arithmetic to keep numbers manageable during calculations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n), where n is the number of rows in the variables array, as each row involves a constant-time modular exponentiation operation. The space complexity is O(n) due to the storage required for the result array containing good indices.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

Increase the size of the array and test the algorithm's scalability with higher values of ai, bi, ci, and mi.
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.
Test cases where all indices are good or none are good, to see if the solution properly handles these extremes.

FAQ

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.

terminal

Solution

Solution 1: Simulation + Fast Power

We can directly simulate according to the problem description. For the power operation modulo, we can use the fast power method to speed up the calculation.

1

2

3

4

5

6

7

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
        ]

Continue Practicing