Sum of special evenly spaced elements in array

Array Dynamic Programming

49.9% acceptance

Mar 31, 2026

You are given a 0-indexed integer array nums consisting of n non-negative integers. You are also given an array queries, where queries[i] = [xi, yi]. The answer to the ith query is the sum of all nums[j] where xi <= j < n and (j - xi) is divisible by yi. Return an array answer where answer.length == queries.length and answer[i] is the answer to the ith query modulo 109 + 7.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn solve(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
    let n = nums.len();
    let modulo = 1_000_000_007i64;
    let threshold = (n as f64).sqrt() as usize + 1;

    // Precompute suffix sums for small steps
    // suffix[y][i] = sum of nums[i], nums[i+y], nums[i+2y], ... mod modulo
    let mut suffix = vec![vec![0i64; n]; threshold + 1];
    for y in 1..=threshold {
      for i in (0..n).rev() {
        suffix[y][i] = nums[i] as i64;
        if i + y < n {
          suffix[y][i] = (suffix[y][i] + suffix[y][i + y]) % modulo;
        }
      }
    }

    let mut result = Vec::with_capacity(queries.len());
    for q in &queries {
      let x = q[0] as usize;
      let y = q[1] as usize;
      if y <= threshold {
        result.push((suffix[y][x] % modulo) as i32);
      } else {
        let mut sum = 0i64;
        let mut j = x;
        while j < n {
          sum = (sum + nums[j] as i64) % modulo;
          j += y;
        }
        result.push(sum as i32);
      }
    }
    result
  }
}