problemmediumalgorithmsleetcode-2961leetcode 2961leetcode2961

Double Modular Exponentiation

MediumUpdated: Aug 2, 2025
Practice on:
LeetCode

Problem

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 ofgood indices 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]
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 <= 10^3
  • 0 <= target <= 10^3

Solution

Method 1 – Modular Exponentiation (Fast Power)

Intuition

We need to compute ((a^b % 10)^c) % m for each variable. Since the numbers can be large, we use modular exponentiation (fast power) to efficiently compute both steps:

  • First, compute a^b % 10 (since the result cycles every 10, this is fast).
  • Then, compute (result)^c % m using modular exponentiation again.

Approach

  1. For each variable [a, b, c, m]:
    • Compute x = pow(a, b, 10) (modular exponentiation for the last digit).
    • Compute y = pow(x, c, m) (modular exponentiation for the final result).
    • If y == target, add the index to the answer.
  2. Return the list of good indices.

Code

C++
class Solution {
public:
    vector<int> getGoodIndices(vector<vector<int>>& variables, int target) {
        vector<int> ans;
        for (int i = 0; i < variables.size(); ++i) {
            int a = variables[i][0], b = variables[i][1], c = variables[i][2], m = variables[i][3];
            int x = 1;
            for (int j = 0; j < b; ++j) x = (x * a) % 10;
            int y = 1;
            for (int j = 0; j < c; ++j) y = (y * x) % m;
            if (y == target) ans.push_back(i);
        }
        return ans;
    }
};
Go
func getGoodIndices(variables [][]int, target int) []int {
    ans := []int{}
    for i, v := range variables {
        a, b, c, m := v[0], v[1], v[2], v[3]
        x := 1
        for j := 0; j < b; j++ {
            x = (x * a) % 10
        }
        y := 1
        for j := 0; j < c; j++ {
            y = (y * x) % m
        }
        if y == target {
            ans = append(ans, i)
        }
    }
    return ans
}
Java
class Solution {
    public List<Integer> getGoodIndices(int[][] variables, int target) {
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < variables.length; ++i) {
            int a = variables[i][0], b = variables[i][1], c = variables[i][2], m = variables[i][3];
            int x = 1;
            for (int j = 0; j < b; ++j) x = (x * a) % 10;
            int y = 1;
            for (int j = 0; j < c; ++j) y = (y * x) % m;
            if (y == target) ans.add(i);
        }
        return ans;
    }
}
Kotlin
class Solution {
    fun getGoodIndices(variables: Array<IntArray>, target: Int): List<Int> {
        val ans = mutableListOf<Int>()
        for (i in variables.indices) {
            val (a, b, c, m) = variables[i]
            var x = 1
            repeat(b) { x = (x * a) % 10 }
            var y = 1
            repeat(c) { y = (y * x) % m }
            if (y == target) ans.add(i)
        }
        return ans
    }
}
Python
class Solution:
    def getGoodIndices(self, variables: list[list[int]], target: int) -> list[int]:
        ans: list[int] = []
        for i, (a, b, c, m) in enumerate(variables):
            x = pow(a, b, 10)
            y = pow(x, c, m)
            if y == target:
                ans.append(i)
        return ans
Rust
impl Solution {
    pub fn get_good_indices(variables: Vec<Vec<i32>>, target: i32) -> Vec<i32> {
        let mut ans = vec![];
        for (i, v) in variables.iter().enumerate() {
            let (a, b, c, m) = (v[0], v[1], v[2], v[3]);
            let x = (0..b).fold(1, |acc, _| acc * a % 10);
            let y = (0..c).fold(1, |acc, _| acc * x % m);
            if y == target {
                ans.push(i as i32);
            }
        }
        ans
    }
}
TypeScript
class Solution {
    getGoodIndices(variables: number[][], target: number): number[] {
        const ans: number[] = [];
        for (let i = 0; i < variables.length; ++i) {
            const [a, b, c, m] = variables[i];
            let x = 1;
            for (let j = 0; j < b; ++j) x = (x * a) % 10;
            let y = 1;
            for (let j = 0; j < c; ++j) y = (y * x) % m;
            if (y === target) ans.push(i);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log b + n log c), where n is the number of variables. Each pow operation is O(log b) and O(log c).
  • 🧺 Space complexity: O(n), for the output list.

Comments