Skip to content

1714. Sum Of Special Evenly-Spaced Elements In Array πŸ”’

Description

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.

 

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.length
  • 1 <= n <= 5 * 104
  • 0 <= nums[i] <= 109
  • 1 <= queries.length <= 1.5 * 105
  • 0 <= xi < n
  • 1 <= yi <= 5 * 104

Solutions

Solution 1: Block Decomposition

Thinking

Each query sums every \(y\)-th element starting at \(x\). Walking the stride per query is too slow when \(q\le 1.5\times 10^5\) and \(n\le 5\times 10^4\), especially for small \(y\).

Large strides are short and can be summed on the fly; small strides are long and should be precomputed. Split at \(\sqrt{n}\).

\(\textit{suf}[i][j]\) is the suffix sum from \(j\) with stride \(i\). Look it up when \(y\le\sqrt{n}\); otherwise scan. The total is \(O((n+q)\sqrt{n})\).

This problem is a typical block decomposition problem. For queries with a large step size, we can directly brute force the solution; for queries with a small step size, we can preprocess the suffix sum of each position and then directly query.

In this problem, we limit the step size of the large step size query to \(\sqrt{n}\), which can ensure that the time complexity of each query is \(O(\sqrt{n})\).

We define a two-dimensional array \(suf\), where \(suf[i][j]\) represents the suffix sum starting from position \(j\) with a step size of \(i\). Then for each query \([x, y]\), we can divide it into two cases:

  • If \(y \le \sqrt{n}\), then we can directly query \(suf[y][x]\);
  • If \(y > \sqrt{n}\), then we can directly brute force the solution.

The time complexity is \(O((n + m) \times \sqrt{n})\), and the space complexity is \(O(n \times \sqrt{n})\). Here, \(n\) is the length of the array, and \(m\) is the number of queries.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def solve(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        mod = 10**9 + 7
        n = len(nums)
        m = int(sqrt(n))
        suf = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(n - 1, -1, -1):
                suf[i][j] = suf[i][min(n, j + i)] + nums[j]
        ans = []
        for x, y in queries:
            if y <= m:
                ans.append(suf[y][x] % mod)
            else:
                ans.append(sum(nums[x::y]) % mod)
        return ans

 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
class Solution {
    public int[] solve(int[] nums, int[][] queries) {
        int n = nums.length;
        int m = (int) Math.sqrt(n);
        final int mod = (int) 1e9 + 7;
        int[][] suf = new int[m + 1][n + 1];
        for (int i = 1; i <= m; ++i) {
            for (int j = n - 1; j >= 0; --j) {
                suf[i][j] = (suf[i][Math.min(n, j + i)] + nums[j]) % mod;
            }
        }
        int k = queries.length;
        int[] ans = new int[k];
        for (int i = 0; i < k; ++i) {
            int x = queries[i][0];
            int y = queries[i][1];
            if (y <= m) {
                ans[i] = suf[y][x];
            } else {
                int s = 0;
                for (int j = x; j < n; j += y) {
                    s = (s + nums[j]) % mod;
                }
                ans[i] = s;
            }
        }
        return ans;
    }
}

 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
class Solution {
public:
    vector<int> solve(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        int m = (int) sqrt(n);
        const int mod = 1e9 + 7;
        int suf[m + 1][n + 1];
        memset(suf, 0, sizeof(suf));
        for (int i = 1; i <= m; ++i) {
            for (int j = n - 1; ~j; --j) {
                suf[i][j] = (suf[i][min(n, j + i)] + nums[j]) % mod;
            }
        }
        vector<int> ans;
        for (auto& q : queries) {
            int x = q[0], y = q[1];
            if (y <= m) {
                ans.push_back(suf[y][x]);
            } else {
                int s = 0;
                for (int i = x; i < n; i += y) {
                    s = (s + nums[i]) % mod;
                }
                ans.push_back(s);
            }
        }
        return ans;
    }
};

 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
func solve(nums []int, queries [][]int) (ans []int) {
    n := len(nums)
    m := int(math.Sqrt(float64(n)))
    const mod int = 1e9 + 7
    suf := make([][]int, m+1)
    for i := range suf {
        suf[i] = make([]int, n+1)
        for j := n - 1; j >= 0; j-- {
            suf[i][j] = (suf[i][min(n, j+i)] + nums[j]) % mod
        }
    }
    for _, q := range queries {
        x, y := q[0], q[1]
        if y <= m {
            ans = append(ans, suf[y][x])
        } else {
            s := 0
            for i := x; i < n; i += y {
                s = (s + nums[i]) % mod
            }
            ans = append(ans, s)
        }
    }
    return
}

 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
function solve(nums: number[], queries: number[][]): number[] {
    const n = nums.length;
    const m = Math.floor(Math.sqrt(n));
    const mod = 10 ** 9 + 7;
    const suf: number[][] = Array(m + 1)
        .fill(0)
        .map(() => Array(n + 1).fill(0));
    for (let i = 1; i <= m; ++i) {
        for (let j = n - 1; j >= 0; --j) {
            suf[i][j] = (suf[i][Math.min(n, j + i)] + nums[j]) % mod;
        }
    }
    const ans: number[] = [];
    for (const [x, y] of queries) {
        if (y <= m) {
            ans.push(suf[y][x]);
        } else {
            let s = 0;
            for (let i = x; i < n; i += y) {
                s = (s + nums[i]) % mod;
            }
            ans.push(s);
        }
    }
    return ans;
}

Comments