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
Aof integers. - A list of queries, where each query is a pair
[val, index].
Outputs:
- An array containing the sum of even numbers in
Aafter each query.
Implicit Constraints/Edge Cases:
- The array
Acan 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
-
Initialize the Sum of Evens:
- Calculate the initial sum of all even numbers in the array
A.
- Calculate the initial sum of all even numbers in the array
-
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.
-
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
mis 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
Ais 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.