LeetCode 2961 - Double Modular Exponentiation

The problem gives us a 0-indexed 2D array called variables, where each element contains four integers: - ai - bi - ci - mi For each index i, we must evaluate the following mathematical expression: If the result equals the given integer target, then index i is considered a good…

leetcodemediumarraymathsimulation

LeetCode Problem 2961

Difficulty: 🟡 Medium
Topics: Array, Math, Simulation

Solution

Problem Understanding

The problem gives us a 0-indexed 2D array called variables, where each element contains four integers:

  • ai
  • bi
  • ci
  • mi

For each index i, we must evaluate the following mathematical expression:

$$((a_i^{b_i} \bmod 10)^{c_i}) \bmod m_i$$

If the result equals the given integer target, then index i is considered a good index.

Our task is to return an array containing all such good indices. The order of the returned indices does not matter.

In simpler terms, for every row [a, b, c, m], we perform two modular exponentiation operations:

  1. Compute a^b % 10
  2. Take that result and compute (result^c) % m

If the final value matches target, we include the row's index in the answer.

The important observation is that the expression contains exponentiation, which can grow extremely quickly. For example, even 1000^1000 is astronomically large and impossible to compute directly. A naive implementation that calculates powers normally would overflow or become computationally infeasible.

Fortunately, the problem structure includes modulo operations, which allows us to use modular exponentiation to efficiently compute powers without generating huge intermediate values.

Understanding the Constraints

The constraints are relatively small:

  • 1 <= variables.length <= 100
  • 1 <= ai, bi, ci, mi <= 1000
  • 0 <= target <= 1000

The number of rows is small, at most 100, but the exponent values can be as large as 1000. Even though 1000 may not seem huge, direct exponentiation like 1000^1000 is still impractical.

These constraints strongly suggest using efficient modular arithmetic, specifically fast exponentiation through built in power functions.

Important Edge Cases

One important edge case is when mi = 1. Since any number modulo 1 is always 0, the final result must always be 0 regardless of earlier calculations.

Another edge case occurs when a^b % 10 = 0. Once the intermediate value becomes 0, any positive power of it remains 0, simplifying the second computation.

We should also consider cases where no index satisfies the condition. In such scenarios, we must correctly return an empty array.

Finally, multiple indices may satisfy the condition, and the problem allows returning them in any order.

Approaches

Brute Force Approach

A straightforward solution is to directly compute the mathematical expression for every row.

For each [a, b, c, m], we could:

  1. Compute a^b
  2. Take % 10
  3. Raise the result to the power c
  4. Take % m
  5. Compare against target

This approach is conceptually simple and obviously correct because it follows the problem statement exactly.

However, it is computationally inefficient because exponentiation grows extremely fast. Values like 1000^1000 are enormous and expensive to compute. Even languages with arbitrary precision integers would spend unnecessary time handling huge numbers.

Key Insight for an Optimal Solution

The crucial observation is that we never need the full exponentiation result.

The problem only asks for:

$$a^b \bmod 10$$

and then:

$$x^c \bmod m$$

This means we can use modular exponentiation, which computes powers while continuously reducing values modulo a number.

Both Python and Go provide efficient power implementations:

  • Python: pow(base, exponent, mod)
  • Go: implement fast exponentiation manually

Instead of computing gigantic numbers, modular exponentiation keeps intermediate values small, making the computation extremely efficient.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n × huge exponentiation cost) O(1) Computes massive powers directly, impractical
Optimal O(n × log b + n × log c) O(1) Uses modular exponentiation to avoid large numbers

Algorithm Walkthrough

  1. Initialize an empty result array to store all good indices.
  2. Iterate through every row in variables using its index.
  3. Extract the four values a, b, c, and m from the current row.
  4. Compute the first modular exponentiation:

$$intermediate = a^b \bmod 10$$

We use modulo 10 because the problem explicitly asks for it. This immediately limits the intermediate value to the range [0, 9]. 5. Compute the second modular exponentiation:

$$final = intermediate^c \bmod m$$

Again, modular exponentiation prevents huge intermediate numbers from forming. 6. Compare final with target.

If they match, append the current index to the result array. 7. After processing all rows, return the result array.

Why it works

The algorithm works because it evaluates the exact mathematical expression required by the problem:

$$((a^b \bmod 10)^c) \bmod m$$

The only optimization is how exponentiation is computed. Modular exponentiation is mathematically equivalent to ordinary exponentiation followed by modulo, but avoids constructing gigantic intermediate numbers. Since every row is checked independently and included only when its result equals target, the algorithm always returns exactly the set of good indices.

Python Solution

from typing import List

class Solution:
    def getGoodIndices(self, variables: List[List[int]], target: int) -> List[int]:
        good_indices = []

        for index, (a, b, c, m) in enumerate(variables):
            intermediate = pow(a, b, 10)
            final_value = pow(intermediate, c, m)

            if final_value == target:
                good_indices.append(index)

        return good_indices

The implementation closely follows the algorithm described earlier.

We first initialize good_indices to store valid indices. Then we iterate through variables using enumerate, which gives both the index and the values in each row.

The expression is evaluated in two stages. First, pow(a, b, 10) efficiently computes a^b % 10. Python's three argument pow() performs modular exponentiation internally, making it much faster than calculating a^b first.

Next, pow(intermediate, c, m) computes the second modular exponentiation.

If the computed value matches target, the index is added to the answer list. After all rows are processed, we return the collected indices.

Go Solution

func modPow(base, exponent, mod int) int {
	result := 1
	base %= mod

	for exponent > 0 {
		if exponent%2 == 1 {
			result = (result * base) % mod
		}

		base = (base * base) % mod
		exponent /= 2
	}

	return result
}

func getGoodIndices(variables [][]int, target int) []int {
	result := []int{}

	for i, variable := range variables {
		a, b, c, m := variable[0], variable[1], variable[2], variable[3]

		intermediate := modPow(a, b, 10)
		finalValue := modPow(intermediate, c, m)

		if finalValue == target {
			result = append(result, i)
		}
	}

	return result
}

The Go implementation follows the same logic as Python but requires a manual implementation of modular exponentiation because Go does not provide a built in pow(base, exponent, mod) function for integers.

The helper function modPow() uses binary exponentiation, also called fast exponentiation. Instead of multiplying the base repeatedly, it repeatedly squares the base and halves the exponent, reducing the complexity to logarithmic time.

Go slices are naturally dynamic, so append() is used to build the result list. Integer overflow is not an issue here because modular reduction happens continuously and the values remain small.

Worked Examples

Example 1

Input:

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

We process each index one by one.

Index a b c m a^b % 10 Final Computation Result Good?
0 2 3 3 10 8 8³ % 10 2 Yes
1 3 3 3 1 7 7³ % 1 0 No
2 6 1 1 4 6 6¹ % 4 2 Yes

Detailed trace:

Index 0

$$2^3 \bmod 10 = 8$$

$$8^3 \bmod 10 = 512 \bmod 10 = 2$$

Since 2 == target, include index 0.

Index 1

$$3^3 \bmod 10 = 27 \bmod 10 = 7$$

$$7^3 \bmod 1 = 0$$

Since 0 != 2, skip it.

Index 2

$$6^1 \bmod 10 = 6$$

$$6^1 \bmod 4 = 2$$

Since 2 == target, include index 2.

Final answer:

[0, 2]

Example 2

Input:

variables = [[39,3,1000,1000]]
target = 17
Index a b c m a^b % 10 Final Result Good?
0 39 3 1000 1000 9 1 No

Detailed trace:

First computation:

$$39^3 \bmod 10$$

Since only the last digit matters:

$$9^3 = 729$$

$$729 \bmod 10 = 9$$

Second computation:

$$9^{1000} \bmod 1000 = 1$$

Since 1 != 17, index 0 is excluded.

Final answer:

[]

Complexity Analysis

Measure Complexity Explanation
Time O(n × (log b + log c)) Each row performs two modular exponentiation operations
Space O(1) Only a few extra variables are used

Since n <= 100, the algorithm is extremely efficient. Modular exponentiation runs in logarithmic time with respect to the exponent, making even exponent values up to 1000 trivial to process.

Test Cases

class Solution:
    def getGoodIndices(self, variables, target):
        good_indices = []

        for index, (a, b, c, m) in enumerate(variables):
            intermediate = pow(a, b, 10)
            final_value = pow(intermediate, c, m)

            if final_value == target:
                good_indices.append(index)

        return good_indices

sol = Solution()

# Example 1
assert sol.getGoodIndices(
    [[2, 3, 3, 10], [3, 3, 3, 1], [6, 1, 1, 4]],
    2
) == [0, 2]  # provided example

# Example 2
assert sol.getGoodIndices(
    [[39, 3, 1000, 1000]],
    17
) == []  # provided example

# Single valid index
assert sol.getGoodIndices(
    [[2, 2, 2, 10]],
    6
) == [0]  # one valid result

# No matching indices
assert sol.getGoodIndices(
    [[2, 2, 2, 10]],
    5
) == []  # no valid index

# mi = 1 always produces 0
assert sol.getGoodIndices(
    [[5, 5, 5, 1]],
    0
) == [0]  # modulo 1 edge case

# Multiple matching indices
assert sol.getGoodIndices(
    [[2, 3, 3, 10], [6, 1, 1, 4]],
    2
) == [0, 1]  # multiple good indices

# Maximum values
assert sol.getGoodIndices(
    [[1000, 1000, 1000, 1000]],
    pow(pow(1000, 1000, 10), 1000, 1000)
) == [0]  # upper constraint stress test

# Intermediate result becomes zero
assert sol.getGoodIndices(
    [[10, 5, 100, 7]],
    0
) == [0]  # 10^5 % 10 = 0

Test Summary

Test Why
Example 1 Verifies correctness on provided sample
Example 2 Verifies empty result case
Single valid index Tests minimal successful input
No matching indices Ensures proper exclusion logic
mi = 1 Validates modulo edge case
Multiple matching indices Confirms multiple indices are collected
Maximum values Stress tests upper constraints
Intermediate becomes zero Ensures zero propagation works correctly

Edge Cases

When mi = 1

This case is important because any number modulo 1 is always 0. A naive implementation might overlook this mathematical property or accidentally divide by zero. Our implementation naturally handles it because modular exponentiation correctly returns 0 when modulo 1 is used.

When No Good Index Exists

Some inputs may produce no matching values. This could cause bugs if the implementation assumes at least one valid result exists. Our solution initializes an empty list and only appends matching indices, so returning [] happens naturally.

When the Intermediate Value Becomes Zero

If a^b % 10 = 0, then the second computation becomes:

$$0^c \bmod m$$

which is always 0 for positive c. This case could cause confusion in manual implementations, especially if exponentiation is written incorrectly. Our use of modular exponentiation handles it automatically and correctly.

Maximum Constraint Values

Inputs such as [1000, 1000, 1000, 1000] involve very large exponentiation. A brute force implementation would struggle with massive intermediate numbers. Our implementation avoids this problem entirely because modular exponentiation keeps values bounded throughout computation.