Leetcode 1714. Sum Of Special Evenly-Spaced Elements In Array
Problem Explanation
Given an integer array nums
of length n
, consisting of non-negative integers, and an array queries
, where each query is represented as a pair [x, y]
. For each query, we need to calculate the sum of all integers in nums
, such that their index j
satisfy the following conditions:
x <= j < n
(j - x) % y == 0
The answer should be returned in an array, where each element is the result of the corresponding query after taking the modulo 10^9 + 7.
Example
Let's go through an example to understand the problem:
Input:
1nums = [0,1,2,3,4,5,6,7] 2queries = [[0,3],[5,1],[4,2]]
-
For query
[0,3]
, we need to find all indicesj
such that(j - 0) % 3 == 0
. The indices satisfying this condition are 0, 3, and 6. So, our sum would benums[0] + nums[3] + nums[6] = 0 + 3 + 6 = 9
. -
For query
[5,1]
, we need to find all indicesj
such that(j - 5) % 1 == 0
. The indices satisfying this condition are 5, 6, and 7. So, our sum would benums[5] + nums[6] + nums[7] = 5 + 6 + 7 = 18
. -
For query
[4,2]
, we need to find all indicesj
such that(j - 4) % 2 == 0
. The indices satisfying this condition are 4 and 6. So, our sum would benums[4] + nums[6] = 4 + 6 = 10
.
Output: [9, 18, 10]
Approach
By observing the problem, we can infer that for a query [x, y]
, we need to iterate from x
to n
with a step size of y
. During this iteration, we will add the values at the respective indices of the nums
array. Finally, for each query, we will take the modulo value and append it to the answer array.
Algorithm
-
Initialize an empty list
answer
. -
For each query
[x, y]
inqueries
, do:a. Initialize a variable
sums
to 0.b. Iterate through the range
x
ton
, with a step size ofy
. For each indexj
in this range, add the value ofnums[j]
tosums
.c. Append the result of
sums
modulo 10^9 + 7 to theanswer
list. -
Return the
answer
list.
Now let's implement the algorithm in different languages:
Python Solution
1class Solution:
2 def solve(self, nums, queries):
3 MOD = 10**9 + 7
4 answer = []
5
6 for x, y in queries:
7 sums = 0
8 for j in range(x, len(nums), y):
9 sums += nums[j]
10 answer.append(sums % MOD)
11
12 return answer
Java Solution
1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5 public List<Integer> solve(int[] nums, int[][] queries) {
6 int MOD = 1000000007;
7 List<Integer> answer = new ArrayList<>();
8
9 for (int[] query : queries) {
10 int x = query[0];
11 int y = query[1];
12 int sums = 0;
13
14 for (int j = x; j < nums.length; j += y) {
15 sums += nums[j];
16 }
17
18 answer.add(sums % MOD);
19 }
20
21 return answer;
22 }
23}
JavaScript Solution
1class Solution {
2 solve(nums, queries) {
3 const MOD = 1000000007;
4 const answer = [];
5
6 for (let query of queries) {
7 const [x, y] = query;
8 let sums = 0;
9
10 for (let j = x; j < nums.length; j += y) {
11 sums += nums[j];
12 }
13
14 answer.push(sums % MOD);
15 }
16
17 return answer;
18 }
19}
C++ Solution
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6 vector<int> solve(vector<int>& nums, vector<vector<int>>& queries) {
7 int MOD = 1000000007;
8 vector<int> answer;
9
10 for (vector<int>& query : queries) {
11 int x = query[0];
12 int y = query[1];
13 int sums = 0;
14
15 for (int j = x; j < nums.size(); j += y) {
16 sums += nums[j];
17 }
18
19 answer.push_back(sums % MOD);
20 }
21
22 return answer;
23 }
24};
C# Solution
1using System.Collections.Generic;
2
3public class Solution {
4 public IList<int> Solve(int[] nums, int[][] queries) {
5 int MOD = 1000000007;
6 List<int> answer = new List<int>();
7
8 foreach (int[] query in queries) {
9 int x = query[0];
10 int y = query[1];
11 int sums = 0;
12
13 for (int j = x; j < nums.Length; j += y) {
14 sums += nums[j];
15 }
16
17 answer.Add(sums % MOD);
18 }
19
20 return answer;
21 }
22}
Conclusion
In conclusion, we went through the process of understanding the problem statement and an example to clarify our understanding. We devised an algorithm to solve the problem and implemented the solution in Python, Java, JavaScript, C++, and C#. This implementation can be used to calculate sums based on the given query conditions on an array of non-negative integers.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.