Welcome to Subscribe On Youtube
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;
}
};
-
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; } } ############ class Solution { public int[] sumEvenAfterQueries(int[] nums, int[][] queries) { int s = 0; for (int num : nums) { if (num % 2 == 0) { s += num; } } int[] ans = new int[queries.length]; int idx = 0; for (int[] q : queries) { int v = q[0], i = q[1]; int old = nums[i]; nums[i] += v; if (nums[i] % 2 == 0 && old % 2 == 0) { s += v; } else if (nums[i] % 2 == 0 && old % 2 != 0) { s += nums[i]; } else if (old % 2 == 0) { s -= old; } ans[idx++] = s; } return ans; } } -
// 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 -
func sumEvenAfterQueries(nums []int, queries [][]int) []int { s := 0 for _, num := range nums { if num%2 == 0 { s += num } } var ans []int for _, q := range queries { v, i := q[0], q[1] old := nums[i] nums[i] += v if nums[i]%2 == 0 && old%2 == 0 { s += v } else if nums[i]%2 == 0 && old%2 != 0 { s += nums[i] } else if old%2 == 0 { s -= old } ans = append(ans, s) } return ans } -
/** * @param {number[]} nums * @param {number[][]} queries * @return {number[]} */ var sumEvenAfterQueries = function (nums, queries) { let s = 0; for (let num of nums) { if (num % 2 == 0) { s += num; } } let ans = []; for (let [v, i] of queries) { const old = nums[i]; nums[i] += v; if (nums[i] % 2 == 0 && old % 2 == 0) { s += v; } else if (nums[i] % 2 == 0 && old % 2 != 0) { s += nums[i]; } else if (old % 2 == 0) { s -= old; } ans.push(s); } return ans; };