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 <stdio.h>
2#include <stdlib.h>
3
4int* sumEvenAfterQueries(int* nums, int numsSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize){
5 int evenSum = 0;
6 for(int i = 0; i < numsSize; i++) {
7 if(nums[i] % 2 == 0) evenSum += nums[i];
8 }
9 int *answer = (int*) malloc(queriesSize * sizeof(int));
10 for(int i = 0; i < queriesSize; i++) {
11 int val = queries[i][0];
12 int index = queries[i][1];
13 if(nums[index] % 2 == 0) evenSum -= nums[index];
14 nums[index] += val;
15 if(nums[index] % 2 == 0) evenSum += nums[index];
16 answer[i] = evenSum;
17 }
18 *returnSize = queriesSize;
19 return answer;
20}We first calculate the initial sum of even numbers. For each query, if the number at the query index in nums is even, we subtract it from the evenSum. We then apply the query change and check if the new number is even. If so, add it to the evenSum. This way, each query is processed 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.
1using namespace std;
vector<int> recomputeEvenSumAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
vector<int> result;
for (const auto& query : queries) {
nums[query[1]] += query[0];
int evenSum = 0;
for (int num : nums) {
if (num % 2 == 0) evenSum += num;
}
result.push_back(evenSum);
}
return result;
}Each query modifies the specified index, and then we recompute the evenSum by iterating over the entire nums array. This method is simpler to follow but not as efficient as maintaining a running evenSum as in the incremental approach.