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:

1
2
3
4
5
6

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:

1
2

Input: nums = [100,200,101,201,102,202,103,203], queries = [[0,7]]
Output: [303]

Constraints:

  • n == nums.length
  • 1 <= n <= 5 * 10^4
  • 0 <= nums[i] <= 10^9
  • 1 <= queries.length <= 1.5 * 10^5
  • 0 <= xi < n
  • 1 <= 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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)