Leetcode 985. Sum of Even Numbers After Queries
Problem Explanation
We are given an array of integers, A
and a queries
array representing the operations to be performed on A
. Each operation consists of adding a specified value to the item at a specific index in A
, and then computing the sum of the even-valued elements.
For each operation (specified by each sub-array in queries
), we should return the sum of the even-valued elements in A
. The final output should be a list of these sums, in the order of operations given in queries
.
Walkthrough
Let's walk through the problem with an example:
Input: A = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
The first operation in queries
says to add 1 to the element at index 0 in A
. After this, A = [2,2,3,4]
and the sum of even numbers is 8 (2+2+4).
The second operation is to add -3 to the element at index 1 in A
. After this, A = [2,-1,3,4]
and the sum of even numbers is 6 (2+4).
The third operation is to add -4 to the element at index 0 in A
. After this, A = [-2,-1,3,4]
and the sum of even numbers is 2 (-2+4).
Finally, the fourth operation is to add 2 to the element at index 3 in A
. After this, A = [-2,-1,3,6]
and the sum of even numbers is 4 (-2+6).
So the output for the given input should be [8,6,2,4].
Approach
The algorithm iterates over the queries
array and for each operation, if the number at the specified index in A
is even, we subtract it from the current sum. Then we add the value from the query to that number, and if it is now even, we add it back to the sum. We then append the current sum to the result array.
Solution
Python Solution
1 2python 3class Solution: 4 def sumEvenAfterQueries(self, A, queries): 5 res = [] 6 sum_ = sum([i for i in A if i % 2 == 0]) # calculate the initial sum of even numbers in A 7 for val, i in queries: 8 if A[i] % 2 == 0: # if the current number is even, subtract it from sum 9 sum_ -= A[i] 10 A[i] += val # add the val to A[i] 11 if A[i] % 2 == 0: # if the updated number is even, add it to sum 12 sum_ += A[i] 13 res.append(sum_) # append the current sum to the result 14 return res
Java Solution
1 2java 3class Solution { 4 public int[] sumEvenAfterQueries(int[] A, int[][] queries) { 5 int sum = 0; 6 for (int num : A) { 7 if (num % 2 == 0) { 8 sum += num; 9 } 10 } 11 int[] res = new int[queries.length]; 12 for (int i = 0; i < queries.length; i++) { 13 int val = queries[i][0]; 14 int index = queries[i][1]; 15 if (A[index] % 2 == 0) { 16 sum -= A[index]; 17 } 18 A[index] += val; 19 if (A[index] % 2 == 0) { 20 sum += A[index]; 21 } 22 res[i] = sum; 23 } 24 return res; 25 } 26}
JavaScript Solution
1 2javascript 3var sumEvenAfterQueries = function(A, queries) { 4 let sum = A.reduce((a, c) => c % 2 === 0 ? a + c : a, 0); 5 return queries.map(([val, idx]) => { 6 if(A[idx] % 2 === 0) { 7 sum -= A[idx]; 8 } 9 A[idx] += val; 10 if(A[idx] % 2 === 0) { 11 sum += A[idx]; 12 } 13 return sum; 14 }); 15};
C++ Solution
1
2cpp
3class Solution {
4public:
5 vector<int> sumEvenAfterQueries(vector<int>& A, vector<vector<int>>& queries) {
6 vector<int> res;
7 int sum = 0;
8 for (int a : A) {
9 if (a % 2 == 0){
10 sum += a;
11 }
12 }
13 for (auto &query : queries) {
14 if (A[query[1]] % 2 == 0) {
15 sum -= A[query[1]];
16 }
17 A[query[1]] += query[0];
18 if (A[query[1]] % 2 == 0) {
19 sum += A[query[1]];
20 }
21 res.push_back(sum);
22 }
23 return res;
24 }
25};
C# Solution
1 2csharp 3public class Solution { 4 public int[] SumEvenAfterQueries(int[] A, int[][] queries) { 5 int sum = 0; 6 foreach(int num in A) { 7 if(num % 2 == 0) sum += num; 8 } 9 int[] result = new int[queries.Length]; 10 for(int i = 0; i < queries.Length; i++) { 11 if(A[queries[i][1]] % 2 == 0) sum -= A[queries[i][1]]; 12 A[queries[i][1]] += queries[i][0]; 13 if(A[queries[i][1]] % 2 == 0) sum += A[queries[i][1]]; 14 result[i] = sum; 15 } 16 return result; 17 } 18}
Ruby Solution
1
2ruby
3def sum_even_after_queries(a, queries)
4 sum = a.reduce(0) do |acc, num|
5 num.even? ? acc + num : acc
6 end
7 queries.map do |val, idx|
8 sum -= a[idx] if a[idx].even?
9 a[idx] += val
10 sum += a[idx] if a[idx].even?
11 sum
12 end
13end
Swift Solution
1 2swift 3class Solution { 4 func sumEvenAfterQueries(_ A: inout [Int], _ queries: [[Int]]) -> [Int] { 5 var sum = 0 6 for num in A { 7 if num % 2 == 0 { sum += num } 8 } 9 var res: [Int] = [] 10 for q in queries { 11 let val = q[0], index = q[1] 12 if A[index] % 2 == 0 { sum -= A[index] } 13 A[index] += val 14 if A[index] % 2 == 0 { sum += A[index] } 15 res.append(sum) 16 } 17 return res 18 } 19}
Go Solution
1 2Go 3func sumEvenAfterQueries(A []int, queries [][]int) []int { 4 sum := 0 5 for _, num := range A { 6 if num % 2 == 0 { 7 sum += num 8 } 9 } 10 res := make([]int, len(queries)) 11 for i, query := range queries { 12 if A[query[1]] % 2 == 0 { 13 sum -= A[query[1]] 14 } 15 A[query[1]] += query[0] 16 if A[query[1]] % 2 == 0 { 17 sum += A[query[1]] 18 } 19 res[i] = sum 20 } 21 return res 22}
All of these solutions first find the sum of all even numbers in the original array. They then iterate over the queries, for each one checking if the target index originally held an even number, and if so removing it from the sum. The value is then added to the target index and checked for evenness again, and if it is, this time it is added to the sum. The sum after each operation is then stored and returned.
This implementation solves the problem with a time complexity of O(N+M) and a space complexity of O(M), where N is the size of the integer array, and M is the number of queries.
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.