Find x value of array i

Array Math Dynamic Programming

37.2% acceptance

Feb 25, 2026

You are given an array of positive integers nums, and a positive integer k. You are allowed to perform an operation once on nums, where in each operation you can remove any non-overlapping prefix and suffix from nums such that nums remains non-empty. Find the x-value of nums: the number of ways to perform this operation so that the product of the remaining elements leaves a remainder of x when divided by k. Return an array result of size k where result[x] is the x-value of nums for 0 <= x <= k-1.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn result_array(nums: Vec<i32>, k: i32) -> Vec<i64> {
    let k = k as usize;
    let n = nums.len();
    let mut dp = vec![0i64; k];
    let mut result = vec![0i64; k];

    for i in 0..n {
      let v = (nums[i] as usize) % k;
      let mut new_dp = vec![0i64; k];
      // New subarray consisting of just nums[i]
      new_dp[v] += 1;
      // Extend all subarrays ending at i-1
      for j in 0..k {
        if dp[j] > 0 {
          new_dp[(j * v) % k] += dp[j];
        }
      }
      dp = new_dp;
      for j in 0..k {
        result[j] += dp[j];
      }
    }

    result
  }
}