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:

1. x <= j < n
2. (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 indices j such that (j - 0) % 3 == 0. The indices satisfying this condition are 0, 3, and 6. So, our sum would be nums[0] + nums[3] + nums[6] = 0 + 3 + 6 = 9.

• For query [5,1], we need to find all indices j such that (j - 5) % 1 == 0. The indices satisfying this condition are 5, 6, and 7. So, our sum would be nums[5] + nums[6] + nums[7] = 5 + 6 + 7 = 18.

• For query [4,2], we need to find all indices j such that (j - 4) % 2 == 0. The indices satisfying this condition are 4 and 6. So, our sum would be nums[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

1. Initialize an empty list answer.

2. For each query [x, y] in queries, do:

   a. Initialize a variable sums to 0.

   b. Iterate through the range x to n, with a step size of y. For each index j in this range, add the value of nums[j] to sums.

   c. Append the result of sums modulo 10^9 + 7 to the answer list.

3. 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.