Sum of Even Numbers After Queries

Difficulty Level Easy
Frequently asked in Indeed
algorithms Array coding Interview interviewprep LeetCode LeetCodeSolutionsViews 2250

Problem Statement

In this problem, we are given an array of integer and array of arrays queries. For the ith query, we will have two parameters, index and val. After each query, we add val to array[index]. We need to find the sum of all even integers in the array after each query, and return it as a vector of integers.

Example

A = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
8 6 2 4
A = [1,2,3,4], queries = [[2,0],[-2,2],[6,0],[4,2]]
6 6 6 6

Approach

Implementation of Sum of Even Numbers After Queries

One basic approach would be:

For each query, update the corresponding element, and then traverse through the whole array to find the sum of all even numbers. But, this approach would take O(N) time for each query leading to O(N * Q) overall time.

We can do better by maintaining a pre sum which is the sum of all even numbers in the array. For each query, we can check whether the element at its index was contributing to the even sum calculated earlier(by checking if A[index] % 2 == 0). If yes, we subtract it from the running sum and update A[index] as A[index] + val. After that, we need to again check if A[index] is even. If yes, we add it to even_sum. This will be the answer for that query as all the other even elements stay unaffected. Hence, we answer each query in O(1) time.

C++ Program

#include <bits/stdc++.h>

using namespace std;

vector<int> sumEvenAfterQueries(vector<int>& A, vector<vector<int>>& queries) {
    int evenSum = 0;

    for(int &x : A) {
        if(x % 2 == 0) {
            evenSum += x;
        }
    }

    int n = queries.size() , val , idx;
    vector <int> ans(n);
    for(int i = 0 ; i < n ; i++) {
        val = queries[i][0] , idx = queries[i][1];
        if(A[idx] % 2 == 0) evenSum -= A[idx];
        A[idx] += val;
        if(A[idx] % 2 == 0) evenSum += A[idx];
        ans[i] = evenSum;
    }

    return ans;
}

int main() {
    vector <int> A = {1 , 2 , 3 , 4};
    vector < vector <int> > queries = {{1 , 0} , {-3 , 1} , {-4 , 0} , {2 , 3}};
    vector <int> ans = sumEvenAfterQueries(A , queries);
    for(int &x : ans)
        cout << x << " ";
    cout << endl;
    return 0;
}

Java Program

class sum_even_after_queries {
    public static void main(String args[]) {
        int[] A = {1 , 2 , 3 , 4};
        int[][] queries = {{1 , 0} , {-3 , 1} , {-4 , 0} , {2 , 3}};
        int[] ans = sumEvenAfterQueries(A , queries);
        for(int x : ans)
            System.out.print(x + " ");
        System.out.println();
    }

    public static int[] sumEvenAfterQueries(int[] A, int[][] queries) {
        int evenSum = 0;

        for(int x : A) {
            if(x % 2 == 0) {
                evenSum += x;
            }
        }
        int n = queries.length , val , idx;
        int[] ans = new int[n];
        for(int i = 0 ; i < n ; i++) {
            val = queries[i][0];
            idx = queries[i][1];

            if(A[idx] % 2 == 0) evenSum -= A[idx];
            A[idx] += val;
            if(A[idx] % 2 == 0) evenSum += A[idx];
            ans[i] = evenSum;
        }

        return ans;
    }
}
8 6 2 4

Complexity Analysis of Sum of Even Numbers After Queries

Time Complexity

O(N + Q), where, N = size of the given array. Q = number of queries. We spend O(N) time to find the even sum and O(Q) time to answer each query.

Space Complexity 

O(1), as we use constant memory space.

Translate »