Sum of Even Numbers After Queries

Problem Statement

• You are given an integer array nums of length n, and an array queries of length m.
• Each query is represented as an array of two integers [val, index].
  • Add val to nums[index].
  • After each query, calculate the sum of the even numbers in the array.

Return an array result where result[i] is the sum of even numbers after the i-th query.

Examples

Example 1:

Input: nums = [1, 2, 3,4]
       queries = [
                  [1, 0],
                  [-3, 1],
                  [-4, 0],
                  [2, 3]
                 ]
Output: [8, 6, 2, 4]

Explanation:
At the beginning, the array is [1,2,3,4].
After adding 1 to nums[0], the array is [2,2,3,4], and the sum of even values is 2 + 2 + 4 = 8.
After adding -3 to nums[1], the array is [2,-1,3,4], and the sum of even values is 2 + 4 = 6.
After adding -4 to nums[0], the array is [-2,-1,3,4], and the sum of even values is -2 + 4 = 2.
After adding 2 to nums[3], the array is [-2,-1,3,6], and the sum of even values is -2 + 6 = 4.

Example 2:

Input: nums = [1]
       queries = [
                  [4, 0]
                 ]
Output: [0]

Different Approaches

1️⃣ Brute Force Approach

For each query, update the element in the array and recalculate the sum of even numbers from scratch.

Steps:

1. For each query, modify the specified element in the nums array.
2. After each query, iterate through the entire array to find all even numbers and compute their sum.
3. Return the list of sums after each query.

Code:

vector<int> sumEvenAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
    vector<int> result;

    for (auto& query : queries) {
        int val = query[0];
        int index = query[1];

        // Apply the query
        nums[index] += val;

        // Recalculate the sum of even numbers
        int evenSum = 0;
        for (int num : nums) {
            if (num % 2 == 0) {
                evenSum += num;
            }
        }
        
        // Store the result after each query
        result.push_back(evenSum);
    }

    return result;
}

Complexity Analysis:

• Time Complexity:
  • For each query, recalculating the sum of even numbers takes O(n), where n is the size of nums.
  • For m queries, the time complexity will be O(m * n), which can be inefficient for large inputs.

2️⃣ Precomputed Even Sum

To optimize the brute-force approach, we keep track of the sum of even numbers and update it incrementally instead of recalculating it from scratch after each query.

Steps:

1. Calculate the initial sum of even numbers in the nums array.
2. For each query:
   • If the original value at nums[index] is even, subtract it from the evenSum.
   • Update the value at nums[index].
   • If the new value at nums[index] is even, add it to evenSum.
3. Store the current evenSum after each query.

Code:

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

    // Step 1: Calculate initial even sum
    for (int num : nums) {
        if (num % 2 == 0) {
            evenSum += num;
        }
    }

    // Step 2: Process each query
    for (const auto& query : queries) {
        int val = query[0];
        int index = query[1];

        // If the current value at index is even, subtract it from evenSum
        if (nums[index] % 2 == 0) {
            evenSum -= nums[index];
        }

        // Update the value at nums[index]
        nums[index] += val;

        // If the new value at index is even, add it to evenSum
        if (nums[index] % 2 == 0) {
            evenSum += nums[index];
        }

        // Store the current evenSum
        result.push_back(evenSum);
    }

    return result;
}

Complexity Analysis:

• Time Complexity:
  • Initial sum calculation takes O(n).
  • Processing each query takes constant time O(1) because we are only updating the even sum for the changed element.
  • For m queries, the overall time complexity is O(n + m).