Domain 1EasyCORE

Sum of Even Numbers After Queries

We are given an array `A` of integers and a series of queries. Each query consists of two values: `val` and `index`. The task is to add `val` to the element at `A[index]`, then compute the sum of all even numbers in the modified array. We need to return an array where each element corresponds to the sum of even numbers after each query.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

985. Sum of Even Numbers After Queries

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 0
Acceptance rate: 60.6%


Problem Breakdown

We are given an array A of integers and a series of queries. Each query consists of two values: val and index. The task is to add val to the element at A[index], then compute the sum of all even numbers in the modified array. We need to return an array where each element corresponds to the sum of even numbers after each query.

Inputs:

  • An initial array A of integers.
  • A list of queries, where each query is a pair [val, index].

Outputs:

  • An array containing the sum of even numbers in A after each query.

Implicit Constraints/Edge Cases:

  • The array A can be empty or contain negative numbers.
  • Queries can modify elements to become even or odd.
  • The number of queries can be large, so efficiency is important.

Intuition

The brute-force approach would involve recalculating the sum of even numbers from scratch after each query. This would result in a time complexity of O(n * m), where n is the length of the array and m is the number of queries, which is inefficient given the constraints.

A better approach is to maintain a running total of the sum of even numbers. When processing each query, we adjust this sum based on whether the element at the specified index was even before the update and whether it becomes even after the update. This reduces the time complexity to O(m), as we only need to consider the affected elements.

Approach

  1. Initialize the Sum of Evens:

    • Calculate the initial sum of all even numbers in the array A.
  2. Process Each Query:

    • For each query, determine the current value at the specified index.
    • If the current value is even, subtract it from the running total of evens (since we are about to modify it).
    • Update the element at the specified index by adding val.
    • Check if the new value is even. If so, add it to the running total of evens.
    • Append the updated sum of evens to the result array.
  3. Return the Result:

    • After processing all queries, return the result array containing the sum of even numbers after each query.

Complexity Analysis

  • Time Complexity: O(m), where m is the number of queries. We process each query in constant time.
  • Space Complexity: O(1) for the running total of evens and O(m) for storing the result array.

Solution

def sumEvenAfterQueries(A, queries):
    # Step 1: Calculate the initial sum of even numbers
    sum_of_evens = sum(x for x in A if x % 2 == 0)
    
    # Step 2: Initialize the result array
    result = []
    
    # Step 3: Process each query
    for val, index in queries:
        # If the current value at index is even, subtract it from the sum_of_evens
        if A[index] % 2 == 0:
            sum_of_evens -= A[index]
        
        # Update the element at the specified index
        A[index] += val
        
        # If the new value at index is even, add it to the sum_of_evens
        if A[index] % 2 == 0:
            sum_of_evens += A[index]
        
        # Append the current sum of evens to the result array
        result.append(sum_of_evens)
    
    # Step 4: Return the result array
    return result

Edge Cases Handled

  • Empty Array: If A is empty, the initial sum of evens is zero, and each query will not change this.
  • Negative Numbers: The solution correctly handles negative numbers by checking if they are even or odd using the modulus operator %.
  • Large Queries: The approach efficiently processes up to 10,000 queries by maintaining a running total of even numbers.