Sponsored
Sponsored
In this approach, we will maintain a running sum of even numbers. For each query, before updating the number at the given index, we check if it's even and subtract it from our running total if it is. After updating, we check if the new number is even and add it to the total if it is. This method avoids recalculating the sum of all even numbers from scratch after each query, thus optimizing the solution.
Time Complexity: O(n + m), where n is the length of nums and m is the number of queries.
Space Complexity: O(1), as we use only constant extra space.
1#include <vector>
2using namespace std;
3
4vector<int> sumEvenAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
5 int evenSum = 0;
6 for (int num : nums) {
7 if (num % 2 == 0) evenSum += num;
8 }
9 vector<int> result;
10 for (const auto& query : queries) {
11 int val = query[0], index = query[1];
12 if (nums[index] % 2 == 0) evenSum -= nums[index];
13 nums[index] += val;
14 if (nums[index] % 2 == 0) evenSum += nums[index];
15 result.push_back(evenSum);
16 }
17 return result;
18}We initialize the evenSum with the sum of initial even elements in nums. For each query, we check if the current indexed value is even. If it is, we subtract it from evenSum. Then, we apply the update and re-check if the value becomes even. If yes, add to evenSum. This approach allows processing each query in constant time.
This approach calculates the sum of even numbers from scratch after each query. Though straightforward, it may not be the most efficient, as it recalculates the sum fully rather than in an incremental manner.
Time Complexity: O(n * m), as the even sum is recalculated n times for each query m.
Space Complexity: O(1), aside from the storage for results.
1
Each query is independently processed by updating the indicated index and recalculating the entire array's evenSum afterward. While direct, this method lacks the efficiency of the first approach as every query starts with a new sum computation.