Sum of Even Numbers After Queries

Sum of Even Numbers After Queries

What is this problem about?

In this problem, you have an initial array of integers and a list of queries. Each query consists of a value val and an index idx. For each query, you add val to the element at nums[idx], and then you need to find the sum of all even numbers in the updated array. You should return an array containing these sums after each query.

Why is this asked in interviews?

Asked by companies like Indeed, this problem tests a candidate's ability to maintain a running total rather than re-calculating everything from scratch. It's a test of efficient "delta updates." If the array and the number of queries are large, re-scanning the array for every query (O(N*Q)) will be too slow. The interviewer wants to see if you can update the sum in O(1) per query.

Algorithmic pattern used

The pattern is "Incremental Update" or "Running Total Management."

1. Calculate the initial sum of all even numbers in the array.
2. For each query:
   • Check if the current value nums[idx] is even. If it is, subtract it from the even_sum.
   • Apply the query: nums[idx] += val.
   • Check if the new value nums[idx] is even. If it is, add it to the even_sum.
   • Store the current even_sum in the result array.

Example explanation

Array: [1, 2, 3, 4]. Initial even numbers are 2 and 4. even_sum = 6. Query: val = 1, idx = 1.

• nums[1] was 2 (even). Subtract 2: even_sum = 4.
• New nums[1] is 2 + 1 = 3 (odd). Don't add anything.
• Result after Query 1: 4. Query: val = 3, idx = 0.
• nums[0] was 1 (odd). Subtract nothing.
• New nums[0] is 1 + 3 = 4 (even). Add 4: even_sum = 4 + 4 = 8.
• Result after Query 2: 8.

Common mistakes candidates make

1. O(N*Q) Solution: Iterating through the entire array after every single query.
2. Condition Confusion: Mismanaging the four cases (even to even, even to odd, odd to even, odd to odd).
3. Updating sum before removing old value: Trying to calculate the delta without first "clearing" the contribution of the element being changed.

Interview preparation tip

Whenever a problem asks for a property after multiple updates, always look for a way to update the previous answer in O(1). This "incremental update" logic is a cornerstone of performance optimization in real-world software.