Formatted question description: https://leetcode.ca/all/1714.html
1714. Sum Of Special Evenly-Spaced Elements In Array
Level
Hard
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] = [x_i, y_i]
. The answer to the i-th
query is the sum of all nums[j]
where x_i <= j < n
and (j - x_i)
is divisible by y_i
.
Return an array answer
where answer.length == queries.length
and answer[i]
is the answer to the i-th
query modulo 10^9 + 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 * 10^4
0 <= nums[i] <= 10^9
1 <= queries.length <= 1.5 * 10^5
0 <= x_i < n
1 <= y_i <= 5 * 10^4
Solution
Let n
be the length of nums
and let sqrt
be the square root of n
. Create a 2D array dp
of n
rows and sqrt - 1
columns, where dp[x][y]
represents the query result of [x, y]
when y
is less than sqrt
. For i
from n - 1
to 0 and for j
from 1 to sqrt - 1
, if i + j < n
, then dp[i][j] = nums[i] + dp[i + j][j]
. Otherwise, dp[i][j] = nums[i]
.
For the i
-th query [x, y]
, if y < sqrt
, then answer[i] = dp[x][y]
. Otherwise, calculate the sum accordingly and let answer[i]
be the sum. Finally, return answer
.
class Solution {
public int[] solve(int[] nums, int[][] queries) {
final int MODULO = 1000000007;
int length = nums.length;
int sqrt = (int) Math.sqrt(length);
int queriesCount = queries.length;
int[] answer = new int[queriesCount];
long[][] dp = new long[length][sqrt];
for (int i = length - 1; i >= 0; i--) {
for (int j = 1; j < sqrt; j++) {
if (i + j < length)
dp[i][j] = (nums[i] + dp[i + j][j]) % MODULO;
else
dp[i][j] = nums[i];
}
}
for (int i = 0; i < queriesCount; i++) {
int x = queries[i][0], y = queries[i][1];
if (y >= sqrt) {
long sum = 0;
while (x < length) {
sum = (sum + nums[x]) % MODULO;
x += y;
}
answer[i] = (int) sum;
} else
answer[i] = (int) dp[x][y];
}
return answer;
}
}