Double modular exponentiation

Array Math Simulation

48.0% acceptance

Feb 25, 2026

123

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: ((aibi % 10)ci) % mi == target Return an array consisting of good indices in any order.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn get_good_indices(variables: Vec<Vec<i32>>, target: i32) -> Vec<i32> {
    fn modpow(mut base: i64, mut exp: i64, modulus: i64) -> i64 {
      let mut result = 1i64;
      base %= modulus;
      while exp > 0 {
        if exp & 1 == 1 { result = result * base % modulus; }
        base = base * base % modulus;
        exp >>= 1;
      }
      result
    }
    variables
      .iter()
      .enumerate()
      .filter(|(_, v)| {
        let a = v[0] as i64;
        let b = v[1] as i64;
        let c = v[2] as i64;
        let m = v[3] as i64;
        let step1 = modpow(a, b, 10);
        let step2 = modpow(step1, c, m);
        step2 == target as i64
      })
      .map(|(i, _)| i as i32)
      .collect()
  }
}