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.length1 <= n <= 5 * 1040 <= nums[i] <= 1091 <= queries.length <= 1.5 * 1050 <= xi < n1 <= yi <= 5 * 104Problem Overview: You receive an integer array and multiple queries [x, y]. Each query asks for the sum of elements starting at index x and jumping by step y: nums[x] + nums[x+y] + nums[x+2y] ... until the index exceeds the array length. The challenge is answering many such queries efficiently without recomputing the sequence every time.
Approach 1: Direct Simulation (Brute Force) (Time: O(q * n / y), Space: O(1))
The simplest method processes each query independently. Start at index x, repeatedly add nums[i], and increment the index by y until you leave the array. This works because the query directly describes the traversal pattern. However, if y is small, the loop may visit many elements, making the worst-case complexity close to O(q * n). This approach is useful for understanding the query structure but becomes too slow when both n and the number of queries are large.
Approach 2: Block Decomposition / Sqrt Optimization with DP (Time: O(n * sqrt(n) + q * sqrt(n)), Space: O(n * sqrt(n)))
The key observation: queries with small step sizes revisit many indices, while large step sizes naturally skip most of the array. Choose a threshold B = sqrt(n). For every step size y ≤ B, precompute answers using dynamic programming. Define dp[y][i] as the sum starting at index i with step y. Compute it backwards: dp[y][i] = nums[i] + (i + y < n ? dp[y][i + y] : 0). This preprocessing takes O(n * B) time.
During queries, if y ≤ B, return dp[y][x] instantly. If y > B, simulate the traversal because the number of visited elements is at most n / y, which is ≤ sqrt(n). This hybrid strategy keeps every query bounded by roughly O(sqrt(n)). The technique is a classic application of sqrt decomposition combined with dynamic programming over an array.
Recommended for interviews: The brute force method demonstrates understanding of the query pattern but does not scale. Interviewers expect the sqrt decomposition optimization. Recognizing that small step sizes repeat across queries and precomputing them with DP shows strong algorithmic intuition and familiarity with query optimization techniques.
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:
y \le \sqrt{n}, then we can directly query suf[y][x];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.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation (Brute Force) | O(q * n / y) worst-case O(qn) | O(1) | Small inputs or very few queries where preprocessing is unnecessary |
| Block Decomposition + DP | O(n√n + q√n) | O(n√n) | Large arrays and many queries; optimal approach used in competitive programming and interviews |
Leetcode 1714. Sum Of Special Evenly-Spaced Elements In Array • Fearless Learner • 131 views views
Watch 1 more video solutions →Practice Sum Of Special Evenly-Spaced Elements In Array with our built-in code editor and test cases.
Practice on FleetCode