Sum Of Even Numbers After Queries - Leetcode Solution

Problem Statement:

We have an array A of integers, and an array queries of queries.

For the i-th query val = queries[i][0], index = queries[i][1], we add val to A[index]. Then, the answer to the i-th query is the sum of the even values of A.

(Here, the given index = queries[i][1] is a 0-based index, and each query permanently modifies the array A.)

Return the answer to all queries. Your answer array should have answer[i] as the answer to the i-th query.

Solution:

To solve this problem, we can first calculate the sum of all even numbers in the initial array A. Then, for each query, we can add the value of val to the corresponding element of A and update the sum of even numbers.

We can do this efficiently by tracking the parity of the elements in the array A. We can maintain two variables: one for the sum of even elements in A and one for the parity of each element in A.

When we add val to A[index], we need to update the parity of A[index] and update the sum of even numbers accordingly. If A[index] was previously even and becomes odd, we subtract A[index] from the sum of even numbers. If A[index] was previously odd and becomes even, we add A[index] to the sum of even numbers.

Here is the Python code for the solution:

def sumEvenAfterQueries(A, queries): res=[] even_sum=sum([x for x in A if x%2==0]) for i in queries: if A[i[1]]%2==0: even_sum-=A[i[1]] A[i[1]]+=i[0] if A[i[1]]%2==0: even_sum+=A[i[1]] res.append(even_sum) return res

Time Complexity:

The time complexity of this solution is O(n+q), where n is the length of the initial array A and q is the number of queries. This is because we need to iterate over A once to calculate the initial sum of even numbers, and we need to iterate over each query once.

Space Complexity:

The space complexity of this solution is O(1), as we are only using constant extra space. We are not using any additional arrays or data structures; we are simply using two variables to track the sum of even numbers and the parity of the elements in A.

1