Taro Logo

Sum of Even Numbers After Queries

#5 Most AskedMedium
4 views
Topics:
Arrays

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


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. Does each query add its value to one index and then ask for the sum of the even numbers?
  2. Can the original numbers and the updates be negative?
  3. Is zero treated as even and included in the sum?
  4. Are the query indexes always inside the array?
  5. Should there be one even-sum answer for every query, in the same order?

Brute Force Solution

Approach

Apply each update directly to the array, then walk the whole array again and add up every even value. That fresh total is the answer for the query. Repeat this for every query, in order.

Here's how the algorithm would work step-by-step:

  1. Take the queries one at a time.
  2. Add the query value to the element at the given index.
  3. Start a new even-sum at zero.
  4. Visit every element and add it when it is even.
  5. Record that sum as the answer for this query.
  6. Continue until every query has an answer.

Code Implementation

class Solution:
    def sumEvenAfterQueries(self, numbers_list: list[int], queries: list[list[int]]) -> list[int]:
        answers_for_each_query = []

        # Process each query one by one as described in the instructions.
        for value_to_add, index_to_modify in queries:
            numbers_list[index_to_modify] += value_to_add

            current_even_sum = 0

            # After each modification, we must recalculate the sum of even numbers from scratch.
            for number in numbers_list:
                # Check if the number is even to decide if it should be included in our sum.
                if number % 2 == 0:
                    current_even_sum += number
            
            answers_for_each_query.append(current_even_sum)

        return answers_for_each_query

Big(O) Analysis

Time Complexity
O(q * n) – Each query changes one element and then scans every element to rebuild the even sum. If there are q queries and n elements, the scans do work proportional to q times n. The update itself is a single addition. The repeated full scans dominate the cost. Answers are produced in the same order as the queries.
Space Complexity
O(1) – The even sum for the current query is a single number. The array is updated in place. No extra copy of the numbers is stored. The list of answers is the required output, and the working memory besides that stays constant.

Optimal Solution

Approach

Keep one running total of the even numbers. Before an update, remove the old value from that total if it was even. After the update, add the new value if it is even. Each query then reports the total without scanning the array again.

Here's how the algorithm would work step-by-step:

  1. Add up the even numbers once, before any query.
  2. For each query, look at the value that is about to change.
  3. If that old value is even, subtract it from the running total.
  4. Add the query value into the array.
  5. If the new value is even, add it to the running total.
  6. Record the running total as this query's answer.

Code Implementation

def sum_even_after_queries(numbers, queries):
    # First, calculate the initial sum of all even numbers in the array.
    current_even_sum = sum(number for number in numbers if number % 2 == 0)
    answer_list = []

    for value_to_add, index_to_modify in queries:
        # If the original number is even, it must be removed from the sum before modification.
        if numbers[index_to_modify] % 2 == 0:
            current_even_sum -= numbers[index_to_modify]

        # Perform the actual modification on the number in the array.
        numbers[index_to_modify] += value_to_add

        # If the new, modified number is even, it should be included in the running sum.
        if numbers[index_to_modify] % 2 == 0:
            current_even_sum += numbers[index_to_modify]

        answer_list.append(current_even_sum)

    return answer_list

Big(O) Analysis

Time Complexity
O(n + q) – The opening pass visits each element once to build the even sum. Every query then does a constant amount of work: inspect the old value, update it, and maybe adjust the total. With n elements and q queries, the total work is proportional to n plus q. The array is never rescanned after the first pass.
Space Complexity
O(1) – The running even sum is a single number. Updates happen in the original array. No frequency map or second copy is needed. Besides the list of answers, extra memory stays constant.

Edge Cases

The array starts with no even numbers and a query creates one
How to Handle:
The new even value is included in the sum for that query.
An even number becomes odd
How to Handle:
That value leaves the even sum on the query that changes it.
An odd number becomes even
How to Handle:
That value joins the even sum after the update.
A value is zero
How to Handle:
Zero is even, so it counts toward the sum.
A negative even number is present
How to Handle:
It is still even, so it is included in the sum.
0/7 completed