Sum of Even Numbers After Queries

Problem Statement

In this problem, you are provided with two arrays: nums (an integer array) and queries. Each element in queries is composed of two integers, where the first integer (vali) represents a value to be added and the second integer (indexi) indicates the position in nums where vali should be added. After applying each query by updating nums[indexi] by adding vali, you need to calculate the sum of all even numbers currently in the nums array. The challenge involves returning an array answer, where each element answer[i] is the computed sum of even numbers after processing the ith query.

Examples

Example 1

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

Input:

nums = [1], queries = [[4,0]]

Output:

[0]

Constraints

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• 1 <= queries.length <= 104
• -104 <= vali <= 104
• 0 <= indexi < nums.length

Approach and Intuition

Given the structure and requirements of the problem, our approach to solving it can be broken down into the following steps:

1. Initialize an output list answer to store the results after each query.
2. Track the sum of even numbers in nums initially before any operations begin. This helps in avoiding recomputation from scratch after each query.
3. Iterate through each query in queries:
   • Extract vali (value to add) and indexi (index to update in nums).
   • Update the integer at position indexi in nums by adding vali.
   • Post-update, check the parity (even or odd) of the updated number and adjust the even sum accordingly:
     • If the updated number at indexi is even, add its value to the sum of evens.
     • If the number at indexi was originally even before updating and has turned odd after updating, subtract its original value (before adding vali) from the sum of evens.
   • Append the current sum of even numbers to the answer list.
4. Finally, return the answer list.

Calculation and Adjustment of Even Sum

• For each query, check the effect of adding vali on the number at indexi.
• Specifically, determine how this update affects whether the number at indexi is even or odd:
  • Increment the overall even sum if a value changes from odd to even.
  • Decrement the overall even sum if a value changes from even to odd.

By leveraging an initially computed even sum and adjusting it dynamically with each update, we achieve an efficient solution by avoiding the necessity to recalculate the sum of even valued elements from scratch for every query.

Solutions

class Solution {
    public int[] calculateEvenSumAfterQueries(int[] nums, int[][] queries) {
        int totalEvenSum = 0;
        for (int num: nums) 
            if (num % 2 == 0) 
                totalEvenSum += num;

        int[] results = new int[queries.length];
        
        for (int j = 0; j < queries.length; j++) {
            int valueToAdd = queries[j][0], targetIndex = queries[j][1];
            if (nums[targetIndex] % 2 == 0) totalEvenSum -= nums[targetIndex];
            nums[targetIndex] += valueToAdd;
            if (nums[targetIndex] % 2 == 0) totalEvenSum += nums[targetIndex];
            results[j] = totalEvenSum;
        }

        return results;
    }
}