Question

Formatted question description: https://leetcode.ca/all/985.html

We have an array A of integers, and an array queries of queries.

For the i-th query val = queries[i][0], index = queries[i][1], we add val to A[index].  Then, the answer to the i-th query is the sum of the even values of A.

(Here, the given index = queries[i][1] is a 0-based index, and each query permanently modifies the array A.)

Return the answer to all queries.  Your answer array should have answer[i] as the answer to the i-th query.

Example 1:

Input: A = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
Output: [8,6,2,4]
Explanation:
At the beginning, the array is [1,2,3,4].
After adding 1 to A[0], the array is [2,2,3,4], and the sum of even values is 2 + 2 + 4 = 8.
After adding -3 to A[1], the array is [2,-1,3,4], and the sum of even values is 2 + 4 = 6.
After adding -4 to A[0], the array is [-2,-1,3,4], and the sum of even values is -2 + 4 = 2.
After adding 2 to A[3], the array is [-2,-1,3,6], and the sum of even values is -2 + 6 = 4.
Note:

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
1 <= queries.length <= 10000
-10000 <= queries[i][0] <= 10000
0 <= queries[i][1] < A.length

Algorithm

This question is given to an array A, saying that each time you can add a value to a number in a certain position of the array, and after each operation, the sum of the even numbers in the current array is returned. Through the examples in the question, you can find that the number added may be negative, and negative even numbers are even numbers. Every time you modify a value, you must return the sum of even numbers. It is definitely not efficient to traverse the array every time to find the sum of even numbers.

In fact, only one number is modified each time. This number has a limited impact on the even number of the entire array , You can discuss it by situation. If the number is an even number before the modification, if it becomes an odd number after the modification, the original even value will be lost. If it is still even after the modification, it is equivalent to losing the original even number first and adding a new even number. If the number is odd before modification, if it is still odd after modification, nothing will be affected. If it becomes even after modification, it is equivalent to adding this even number.

So in summary, first judge the number before the modification, if it is an even number, then subtract the even number, and then judge the modified number, if it is an even number, add the even number. In this case, you only need to traverse the array at the beginning to find the sum of all the even numbers, and then you can quickly get the sum of the even numbers by following the above steps when modifying the number. See the code as follows:

Code

C++

class Solution {
public:
    vector<int> sumEvenAfterQueries(vector<int>& A, vector<vector<int>>& queries) {
        vector<int> res;
        int n = A.size(), even = 0;
        for (int num : A) {
            if (num % 2 == 0) even += num;
        }
        for (auto &query : queries) {
            int old = A[query[1]], cur = old + query[0];
            if (old % 2 == 0) even -= old;
            if (cur % 2 == 0) even += cur;
            A[query[1]] = cur;
            res.push_back(even);
        }
        return res;
    }
};

Java

class Solution {
    public int[] sumEvenAfterQueries(int[] A, int[][] queries) {
        int evenSum = 0;
        for (int num : A) {
            if (num % 2 == 0)
                evenSum += num;
        }
        int length = queries.length;
        int[] sumEvenEachQuery = new int[length];
        for (int i = 0; i < length; i++) {
            int[] query = queries[i];
            int value = query[0], index = query[1];
            int num = A[index];
            int newNum = num + value;
            A[index] = newNum;
            if (num % 2 == 0)
                evenSum -= num;
            if (newNum % 2 == 0)
                evenSum += newNum;
            sumEvenEachQuery[i] = evenSum;
        }
        return sumEvenEachQuery;
    }
}

// OJ: https://leetcode.com/problems/sum-of-even-numbers-after-queries/
// Time: O(A + Q)
// Space: O(1)
class Solution {
public:
    vector<int> sumEvenAfterQueries(vector<int>& A, vector<vector<int>>& queries) {
        vector<int> ans(queries.size());
        int sum = 0;
        for (int n : A) {
            if (n % 2 == 0) sum += n;
        }
        for (int i = 0; i < queries.size(); ++i) {
            auto q = queries[i];
            int val = q[0], index = q[1], prev = A[index];
            A[index] += val;
            bool wasEven = prev % 2 == 0, even = A[index] % 2 == 0;
            if (wasEven && even) {
                ans[i] = (sum += val);
            } else if (wasEven && !even) {
                ans[i] = (sum -= prev);
            } else if (!wasEven && even) {
                ans[i] = (sum += A[index]);
            } else ans[i] = sum;
        }
        return ans;
    }
};

class Solution:
    def sumEvenAfterQueries(
        self, nums: List[int], queries: List[List[int]]
    ) -> List[int]:
        ans = []
        s = sum(num for num in nums if num % 2 == 0)
        for v, i in queries:
            old = nums[i]
            nums[i] += v
            if nums[i] % 2 == 0 and old % 2 == 0:
                s += v
            elif nums[i] % 2 == 0 and old % 2 == 1:
                s += nums[i]
            elif old % 2 == 0:
                s -= old
            ans.append(s)
        return ans

############

# 985. Sum of Even Numbers After Queries
# https://leetcode.com/problems/sum-of-even-numbers-after-queries/

class Solution:
    def sumEvenAfterQueries(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        odd = even = 0
        res = []
        
        for x in nums:
            if x % 2 == 0:
                even += x
            else:
                odd += x
        
        for val, index in queries:
            updated = nums[index] + val
            if nums[index] % 2 == 0:
                if updated % 2 == 0:
                    even += val
                else:
                    even -= nums[index]
                    odd += updated
            else:
                if updated % 2 == 0:
                    odd -= nums[index]
                    even += updated
                else:
                    odd += val
            
            res.append(even)
            nums[index] = updated
        
        return res

985 - Sum of Even Numbers After Queries

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions