Sum Of Special Evenly-Spaced Elements In Array
HardUpdated: Aug 2, 2025
Practice on:
Problem
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 arrayanswer whereanswer.length == queries.length
andanswer[i]is the answer to theith _querymodulo _109 + 7.
Examples
Example 1:
Input: nums = [0,1,2,3,4,5,6,7], queries = [[0,3],[5,1],[4,2]]
Output: [9,18,10]
Explanation: The answers of the queries are as follows:
1) The j indices that satisfy this query are 0, 3, and 6. nums[0] + nums[3] + nums[6] = 9
2) The j indices that satisfy this query are 5, 6, and 7. nums[5] + nums[6] + nums[7] = 18
3) The j indices that satisfy this query are 4 and 6. nums[4] + nums[6] = 10
Example 2:
Input: nums = [100,200,101,201,102,202,103,203], queries = [[0,7]]
Output: [303]
Constraints:
n == nums.length1 <= n <= 5 * 10^40 <= nums[i] <= 10^91 <= queries.length <= 1.5 * 10^50 <= xi < n1 <= yi <= 5 * 10^4
Solution
Approach
For each query [xi, yi], sum all nums[j] where j >= xi and (j - xi) % yi == 0. For small yi, we can precompute prefix sums for each possible remainder. For large yi, we can process each query directly. A hybrid approach is used for efficiency.
Code
C++
#include <vector>
using namespace std;
class Solution {
public:
vector<int> solve(vector<int>& nums, vector<vector<int>>& queries) {
const int MOD = 1e9+7, n = nums.size(), Q = queries.size(), B = 224;
vector<int> res(Q);
vector<vector<long>> presum(B, vector<long>(B));
for (int y = 1; y < B; ++y) {
for (int r = 0; r < y; ++r) {
long sum = 0;
for (int i = r; i < n; i += y) sum = (sum + nums[i]) % MOD;
presum[y][r] = sum;
}
}
for (int qi = 0; qi < Q; ++qi) {
int x = queries[qi][0], y = queries[qi][1];
if (y < B) {
res[qi] = presum[y][x % y];
if (x % y > x) res[qi] = 0;
else {
int first = x;
int last = (n-1) - ((n-1-x)%y);
if (first > last) res[qi] = 0;
}
} else {
long sum = 0;
for (int i = x; i < n; i += y) sum = (sum + nums[i]) % MOD;
res[qi] = sum;
}
}
return res;
}
};
Java
import java.util.*;
class Solution {
public int[] solve(int[] nums, int[][] queries) {
int MOD = 1_000_000_007, n = nums.length, Q = queries.length, B = 224;
int[] res = new int[Q];
long[][] presum = new long[B][B];
for (int y = 1; y < B; ++y) {
for (int r = 0; r < y; ++r) {
long sum = 0;
for (int i = r; i < n; i += y) sum = (sum + nums[i]) % MOD;
presum[y][r] = sum;
}
}
for (int qi = 0; qi < Q; ++qi) {
int x = queries[qi][0], y = queries[qi][1];
if (y < B) {
res[qi] = (int)presum[y][x % y];
} else {
long sum = 0;
for (int i = x; i < n; i += y) sum = (sum + nums[i]) % MOD;
res[qi] = (int)sum;
}
}
return res;
}
}
Kotlin
class Solution {
fun solve(nums: IntArray, queries: Array<IntArray>): IntArray {
val MOD = 1_000_000_007
val n = nums.size
val Q = queries.size
val B = 224
val res = IntArray(Q)
val presum = Array(B) { LongArray(B) }
for (y in 1 until B) {
for (r in 0 until y) {
var sum = 0L
var i = r
while (i < n) {
sum = (sum + nums[i]) % MOD
i += y
}
presum[y][r] = sum
}
}
for (qi in 0 until Q) {
val x = queries[qi][0]
val y = queries[qi][1]
if (y < B) {
res[qi] = presum[y][x % y].toInt()
} else {
var sum = 0L
var i = x
while (i < n) {
sum = (sum + nums[i]) % MOD
i += y
}
res[qi] = sum.toInt()
}
}
return res
}
}
Python
class Solution:
def solve(self, nums: list[int], queries: list[list[int]]) -> list[int]:
MOD = 10**9 + 7
n, Q, B = len(nums), len(queries), 224
presum = [[0]*B for _ in range(B)]
for y in range(1, B):
for r in range(y):
presum[y][r] = sum(nums[i] for i in range(r, n, y)) % MOD
res = [0]*Q
for qi, (x, y) in enumerate(queries):
if y < B:
res[qi] = presum[y][x % y]
else:
res[qi] = sum(nums[i] for i in range(x, n, y)) % MOD
return res
Rust
impl Solution {
pub fn solve(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
const MOD: i64 = 1_000_000_007;
let n = nums.len();
let q = queries.len();
let b = 224;
let mut presum = vec![vec![0i64; b]; b];
for y in 1..b {
for r in 0..y {
let mut sum = 0i64;
let mut i = r;
while i < n {
sum = (sum + nums[i] as i64) % MOD;
i += y;
}
presum[y][r] = sum;
}
}
let mut res = vec![0i32; q];
for (qi, qr) in queries.iter().enumerate() {
let x = qr[0] as usize;
let y = qr[1] as usize;
if y < b {
res[qi] = presum[y][x % y] as i32;
} else {
let mut sum = 0i64;
let mut i = x;
while i < n {
sum = (sum + nums[i] as i64) % MOD;
i += y;
}
res[qi] = sum as i32;
}
}
res
}
}
TypeScript
function solve(nums: number[], queries: number[][]): number[] {
const MOD = 1e9 + 7, n = nums.length, Q = queries.length, B = 224;
const presum: number[][] = Array.from({length: B}, () => Array(B).fill(0));
for (let y = 1; y < B; ++y) {
for (let r = 0; r < y; ++r) {
let sum = 0;
for (let i = r; i < n; i += y) sum = (sum + nums[i]) % MOD;
presum[y][r] = sum;
}
}
const res = new Array(Q).fill(0);
for (let qi = 0; qi < Q; ++qi) {
const [x, y] = queries[qi];
if (y < B) {
res[qi] = presum[y][x % y];
} else {
let sum = 0;
for (let i = x; i < n; i += y) sum = (sum + nums[i]) % MOD;
res[qi] = sum;
}
}
return res;
}
Complexity
- ⏰ Time complexity:
O(n√n + Q) - 🧺 Space complexity:
O(n√n)