Skip to main content
Talentd

Double Modular Exponentiation - Solution & Explanation

MediumArrayMathSimulation9 min readAsked at: Barclays
Practice this problem

Problem Statement

You are given a 0-indexed 2D array variables where variables[i] = [ai, bi, ci, mi], and an integer target.

An index i is good if the following formula holds:

  • 0 <= i < variables.length
  • ((aibi % 10)ci) % mi == target

Return an array consisting of good indices in any order.

 

Example 1:

Input: variables = [[2,3,3,10],[3,3,3,1],[6,1,1,4]], target = 2
Output: [0,2]
Explanation: For each index i in the variables array:
1) For the index 0, variables[0] = [2,3,3,10], (23 % 10)3 % 10 = 2.
2) For the index 1, variables[1] = [3,3,3,1], (33 % 10)3 % 1 = 0.
3) 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: []
Explanation: For each index i in the variables array:
1) 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

Approach Overview

Problem Overview: You receive an array variables where each element contains four integers [a, b, c, m]. For every entry, compute ((a^b % 10)^c) % m and return the indices where the result equals a given target. The challenge is evaluating exponentiation safely without overflow while processing multiple entries.

Approach 1: Naive Simulation (O(n * (b + c)) time, O(1) space)

Iterate through each element in the array and simulate the exponentiation directly. Compute a^b with repeated multiplication, take % 10, then raise the result to the power c and apply % m. This works because the first modulus keeps numbers small, but repeated multiplication still makes the runtime proportional to b + c. It is easy to implement and mirrors the mathematical expression step by step, making it a reasonable baseline for understanding the problem.

Approach 2: Optimized Modular Exponentiation (O(n * (log b + log c)) time, O(1) space)

The efficient solution applies fast exponentiation from modular arithmetic. Instead of multiplying a by itself b times, compute a^b % 10 using binary exponentiation. This technique repeatedly squares the base and halves the exponent, reducing the complexity from linear to logarithmic. After obtaining the first modular result, apply the same fast exponentiation method again to compute (result^c) % m. The algorithm runs in logarithmic time per exponent and avoids large intermediate numbers, which makes it the preferred method for problems involving repeated powers and mod operations.

The process is mostly simulation combined with careful math optimization. Each element is processed independently, so the algorithm scales linearly with the number of rows in the input.

Recommended for interviews: Interviewers expect the optimized modular exponentiation approach. Starting with the naive simulation shows you understand the formula, but switching to binary exponentiation demonstrates knowledge of efficient power computation and modular arithmetic. This optimization reduces exponent handling from linear to logarithmic time, which is a common requirement in coding interviews involving large powers.

Approach 1: Naive Approach

This approach involves direct computation of the formula for each index. We iterate over each variable, compute the exponential terms, and check if the result matches the target.

The function iterates through the variables list and computes the value of the formula using Python's built-in pow function for modular exponentiation. If the result equals the target, the index is considered good and appended to the result list.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n * b * c), because we calculate exponential values directly.
Space Complexity: O(1), as we do not use any extra space apart from storing results.

Try this approach in the editor →

Approach 2: Optimized Modular Exponentiation

This approach leverages the method of modular exponentiation which allows efficient computation of large powers mod m. Instead of computing power directly, it uses recursion or iterative squaring.

The function mod_exp implements modular exponentiation by squaring. This reduces time complexity and efficiently computes large powers. For each variable, we compute the intermediate power modulo 10 and apply the method again for modulus m computation.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n * log(b) + log(c)), where n is the number of equations.
Space Complexity: O(1), marginal storage required beyond result.

Try this approach in the editor →

Approach 3: 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.

The time complexity is O(n times log M), where n is the length of the array variables; and M is the maximum value in b_i and c_i, in this problem M \le 10^3. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Naive Approach

Time Complexity: O(n * b * c), because we calculate exponential values directly.
Space Complexity: O(1), as we do not use any extra space apart from storing results.

Optimized Modular Exponentiation

Time Complexity: O(n * log(b) + log(c)), where n is the number of equations.
Space Complexity: O(1), marginal storage required beyond result.

Simulation + Fast Power—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive SimulationO(n * (b + c))O(1)Useful for understanding the formula or when exponents are very small
Optimized Modular ExponentiationO(n * (log b + log c))O(1)General case with large exponents; avoids overflow and improves performance

Video Solution

2961 Double Modular Exponentiation || Exponentiation 🔥 • Ayush Rao • 581 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Double Modular Exponentiation easy or hard?
Double Modular Exponentiation is considered a medium difficulty problem. The main challenge is recognizing that naive exponentiation is inefficient and replacing it with binary exponentiation. Once you apply modular arithmetic correctly, the implementation becomes straightforward.
Double Modular Exponentiation Python/Java solution
Python and Java solutions typically implement a fast power function that computes (base^exp) % mod using binary exponentiation. The algorithm iteratively squares the base, multiplies when the exponent bit is set, and reduces using modulo each step. This avoids overflow and keeps numbers small throughout the computation.
How to solve Double Modular Exponentiation in O(n)?
Strict O(n) is not achievable because exponentiation depends on the size of the exponents. The practical optimal solution is O(n * (log b + log c)) using fast modular exponentiation. Each array element is processed independently while computing powers in logarithmic time.
What is the best approach for Double Modular Exponentiation?
The most efficient approach uses fast modular exponentiation (binary exponentiation). Instead of computing powers directly, it repeatedly squares the base and halves the exponent while applying modulo operations. This reduces exponent computation from O(b) to O(log b). For each array element, compute a^b % 10 and then apply fast exponentiation again for the second power.
Is Double Modular Exponentiation asked at Google/Amazon/Meta?
Problems involving modular exponentiation and fast power frequently appear in interviews at companies like Google, Amazon, and Meta. They often test understanding of binary exponentiation, overflow prevention, and modular arithmetic. Variants appear in algorithm rounds and competitive programming problems.
What data structure is used in Double Modular Exponentiation?
The problem primarily uses an array to store input values. The main focus is mathematical computation rather than complex data structures. Efficient modular arithmetic and exponentiation logic drive the solution.
What is the time complexity of Double Modular Exponentiation?
The optimized solution runs in O(n * (log b + log c)) time, where n is the number of rows in the variables array. Each exponentiation uses binary exponentiation, which processes the exponent in logarithmic time. Space complexity remains O(1) because only a few variables are maintained during computation.

Ready to solve this problem?

Practice Double Modular Exponentiation with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays