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.