{x}
blog image

Sum of Even Numbers After Queries

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.

 

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

Solution Explanation

This problem asks to calculate the sum of even numbers in an array after applying a series of queries. Each query involves adding a value to a specific element in the array. Instead of recalculating the sum of even numbers from scratch after each query, which would be inefficient, a more optimized approach is used.

Algorithm:

  1. Initial Sum: Calculate the initial sum of even numbers in the nums array. This is done in a single pass.

  2. Iterate Through Queries: Process each query from the queries array.

  3. Update Sum: For each query [val, index]:

    • Check if the current element at nums[index] is even. If it is, subtract it from the current sum of even numbers (s). This is because we're about to modify this element.
    • Update the element nums[index] by adding val.
    • Check if the updated element nums[index] is even. If it is, add it to the current sum of even numbers (s).
    • Append the current s to the ans array. This s represents the sum of even numbers after applying the current query.

  4. Return Result: Return the ans array containing the sum of even numbers after each query.

Time Complexity Analysis:

  • Initial sum calculation: O(N), where N is the length of nums array. This step iterates through the array once.
  • Query processing: O(M), where M is the number of queries. Each query involves a constant number of operations (a few checks and additions/subtractions).
  • Total Time Complexity: O(N + M). The dominant factor will be the larger of N and M.

Space Complexity Analysis:

  • The algorithm uses a constant amount of extra space to store variables like s and ans. The space used by ans is proportional to the number of queries (M).
  • Total Space Complexity: O(M)

Code Examples (Python, Java, C++, Go, TypeScript, Javascript):

The code examples in various languages provided earlier demonstrate this algorithm. All versions have the same core logic: They first calculate the sum of even numbers, then iteratively update this sum based on each query, ensuring that only even numbers are included in the sum. The slight differences between languages reflect their syntax and standard libraries. For example, the way arrays are handled, and the use of for...of loops versus standard for loops.