Abstract / Summary

Compute a base raised to a power modulo two different numbers and return the two results.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 47% (50k+ submissions).

Typical patterns to solve this problem:

• Array
• Math
• Simulation

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution class implements a generator method getGoodIndices that processes a collection of integer quadruples. For each quadruple the method computes a nested modular exponentiation and yields the index of the element when the final result matches a given target value. The design leverages Python’s built-in pow function with three arguments to perform modular exponentiation efficiently, avoiding the need for explicit loops or large intermediate numbers.

Core Logic

The method signature declares two parameters: variables, a list of lists where each inner list contains four integers, and target, an integer to compare against. The method iterates over variables using enumerate, which supplies both the current index i and the unpacked tuple (a, b, c, m). The unpacking step extracts the base, two exponents, and the modulus for each entry.

for i, (a, b, c, m) in enumerate(variables):

The first computational step calculates the remainder of a raised to the power b modulo 10. By passing three arguments to pow, the operation is performed with modular reduction at each multiplication step, keeping the intermediate value bounded by 10.

inner = pow(a, b, 10)

The second step raises the previously obtained inner value to the power c modulo m. Again, the three-argument form of pow ensures that the calculation stays within the range of the modulus m, preventing overflow and reducing the number of arithmetic operations required.

outer = pow(inner, c, m)

A comparison follows; if outer equals the supplied target, the method yields the current index i. Because the method uses yield, it returns a generator rather than a concrete list, allowing the caller to iterate lazily and stop early if desired.

if outer == target:
    yield i

Edge Cases Handled

The implementation implicitly accommodates several edge conditions:

When the exponent b is zero, pow(a, 0, 10) returns 1 modulo 10, which aligns with the mathematical definition that any non-zero base raised to the zero power equals one. This case is handled without special code because the built-in pow correctly returns 1 even when the modulus is present.

When the modulus m equals 1, the second pow call reduces any base to 0 modulo 1. The code correctly yields indices where target is 0, reflecting the fact that any integer modulo 1 is zero.

If c is zero, the second exponentiation yields 1 modulo m (or 0 when m is 1). The built-in pow again respects this rule, so the method correctly identifies indices where the nested computation collapses to 1 (or 0) without additional checks.

When a is negative, the first modular exponentiation still produces a non-negative remainder in the range [0, 9] because Python’s modular arithmetic returns a result with the sign of the divisor. Consequently, the subsequent exponentiation works with a valid non-negative base, and the comparison against target remains accurate.

If variables is empty, the for loop never executes, and the generator yields no values, which is a natural and correct behavior for an empty input set.

Performance Optimizations

The code’s primary performance advantage stems from the use of Python’s three-argument pow function. This variant implements exponentiation by squaring combined with modular reduction, achieving logarithmic time in the exponent while keeping intermediate results bounded by the modulus. By applying this technique twice-first with a small modulus 10 and then with the provided modulus m-the method avoids constructing large intermediate numbers that would arise from naïve exponentiation.

Because the method yields indices lazily, it does not allocate an entire result list up front. Consumers can stop iteration as soon as they have collected the needed indices, which can save both time and memory when only a subset of matches is required.

The unpacking of each quadruple directly in the for loop header eliminates the need for additional indexing operations inside the loop body, reducing overhead per iteration. Enumerating the list provides the index without a separate counter variable, streamlining the control flow.

Overall, the combination of built-in modular exponentiation, lazy generation, and concise unpacking yields a solution that is both computationally efficient and memory-conservative for the problem it addresses.

Imagine a big magical chest filled with smaller boxes, and each box has four secret numbers written on it. The task is to look at every box one by one to see if the numbers inside follow a special rule.

For each box, the first number is used as a base and the second number tells how many times to multiply it by itself. Then, the result is divided by ten, and the leftover part is kept. That leftover part is then multiplied by itself a third time, but this time it is divided by the fourth number, and the new remainder is compared to a target goal.

If that final remainder matches the target goal, the box is considered a winner, and the position of that box in the row is written down. This keeps happening for every single box until there are no more boxes left to check. It is just like sorting through a pile of toys to find all the ones that are the color blue.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster		Java	C++		Python	TS
	WalkCCC		Java	C++		Python
	leetcode.ca		Java	C++	Go	Python	TS
	Progiez		Java	C++		Python
github	charles-wangkai		Java
	everthis	JS
	fsq			C++
	JoshCrozier	JS
	varunu28		Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality