Watch 2 video solutions for Sum Of Special Evenly-Spaced Elements In Array, a hard level problem involving Array, Dynamic Programming. This walkthrough by Fearless Learner has 131 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |