Problem

You are given an integer array nums and an array queries where queries[i] = [vali, indexi].

For each query i, first, apply nums[indexi] = nums[indexi] + vali, then print the sum of the even values of nums.

Return an integer array answer where answer[i] is the answer to the ith query.

Examples

Example 1:

1
2
3
4
5
6
7
8

Input:
nums = [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 nums[0], the array is [2,2,3,4], and the sum of even values is 2 + 2 + 4 = 8.
After adding -3 to nums[1], the array is [2,-1,3,4], and the sum of even values is 2 + 4 = 6.
After adding -4 to nums[0], the array is [-2,-1,3,4], and the sum of even values is -2 + 4 = 2.
After adding 2 to nums[3], the array is [-2,-1,3,6], and the sum of even values is -2 + 6 = 4.

Example 2:

1
2
3

Input:
nums = [1], queries = [[4,0]]
Output: [0]

Solution

Method 1 - 2 Pass with Updation of Even Sums

  1. Calculate the sum of even numbers in array
  2. Now we go through queries.
    1. For each query, we calculate the new number’s value
    2. We check if new number’s value is even. If yes, we check if original number was even. If yes, then we just increment by query value, else we just add new value, as this number converted from odd to even
    3. Else if new number is not even, and existing number was even, just remove it from evenSum, as it was even earlier, but now odd.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public int[] sumEvenAfterQueries(int[] nums, int[][] queries) {
	int evenSum = 0;
	for (int num: nums) {
		if (num % 2 == 0) {
			evenSum += num;
		}
		
	}
	int[] ans = new int[queries.length];
	int k = 0;
	for (int[] query: queries) {
		int v = query[0], idx = query[1];
		int tmpV = nums[idx] + v;
		if(tmpV % 2 == 0) {
			if (nums[idx] % 2 == 0 ) {
				evenSum += v;
			}else {
				evenSum += tmpV;
			}
		}else {
			if (nums[idx] % 2 == 0 ) {
				evenSum -= nums[idx];
			}
		}
		ans[k++] = evenSum;
		nums[idx] = tmpV;
	}
	return ans;
}
 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

    public int[] sumEvenAfterQueries(int[] nums, int[][] queries) {
    	int evenSum = 0, n = queries.length;
    	// calculate the sum of all even numbers
    	for (int x: nums) {
    		if (x % 2 == 0) {
    			evenSum += x;
    		}
    	}
    	int[] ans = new int[n];
    	for (int i = 0; i<n; i++) {
    		int val = queries[i][0], idx = queries[i][1];
    		// if original nums[idx] is even, then we deduct it from evenSum
    		if (nums[idx] % 2 == 0) evenSum -= nums[idx];
    		// in-place update nums
    		nums[idx] += val;
    		// check if we need to update evenSum for the new value
    		if (nums[idx] % 2 == 0) evenSum += nums[idx];
    		// then we have evenSum after this query, push it to ans 
    		ans[i] = evenSum;
    	}
    	return ans;
    }

Complexity

  • Time: O(n)
  • Space: O(1)