Sum of Even Numbers After Queries
MedPrompt
You are given an integer array nums and an array queries where queries[i] = [vali, indexi].
For each query i, first, apply nums[indexi] = nums[indexi] + vali, then print the sum of the even values of nums.
Return an integer array answer where answer[i] is the answer to the ith query.
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]
Constraints:
1 <= nums.length <= 104-104 <= nums[i] <= 1041 <= queries.length <= 104-104 <= vali <= 1040 <= indexi < nums.length
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. For each query, it first updates the element in the nums array and then iterates through the entire modified array to calculate the sum of all even numbers. This process is repeated for every single query.
Algorithm
- Initialize an integer array
answerwith the same length asqueries. - Iterate through each query
[val, index]fromi = 0toqueries.length - 1. - Update the
numsarray:nums[index] = nums[index] + val. - Initialize a variable
currentEvenSum = 0. - Iterate through each number
numin thenumsarray. - If
numis even (num % 2 == 0), add it tocurrentEvenSum. - After the inner loop, store the result:
answer[i] = currentEvenSum. - Return the
answerarray after the outer loop finishes.
Walkthrough
The core idea is to treat each query independently. We loop through the queries array. Inside the loop, for a given query [val, index], we first perform the update nums[index] += val. After the update, we initialize a temporary sum variable to zero. We then loop through all elements of the nums array. For each element, we check if it's even using the modulo operator (%). If it is, we add its value to our temporary sum. Once this inner loop is complete, the temporary sum holds the total sum of even numbers for the current state of the array, which we then store in our result array. This is straightforward but inefficient because we repeatedly scan the entire nums array.
class Solution { public int[] sumEvenAfterQueries(int[] nums, int[][] queries) { int[] answer = new int[queries.length]; for (int i = 0; i < queries.length; i++) { int val = queries[i][0]; int index = queries[i][1]; // Apply the query nums[index] += val; // Calculate the sum of even numbers int currentEvenSum = 0; for (int num : nums) { if (num % 2 == 0) { currentEvenSum += num; } } // Store the result for this query answer[i] = currentEvenSum; } return answer; }}Complexity
Time
O(N * Q), where N is the length of `nums` and Q is the length of `queries`. For each of the Q queries, we iterate through all N elements of the `nums` array to calculate the sum.
Space
O(Q) or O(1). We need an array of size Q to store the answers. If the output array is not considered extra space, the space complexity is O(1).
Trade-offs
Pros
Simple to understand and implement.
Directly follows the problem statement.
Cons
Inefficient for large inputs, as it performs a lot of redundant calculations.
Likely to result in a 'Time Limit Exceeded' error on platforms with strict time limits.
Solutions
Solution
public class Solution { public int [] SumEvenAfterQueries ( int [] nums , int [][] queries ) { int s = nums . Where ( x => x % 2 == 0 ). Sum (); int [] ans = new int [ queries . Length ]; for ( int j = 0 ; j < queries . Length ; j ++) { int v = queries [ j ][ 0 ], i = queries [ j ][ 1 ]; if ( nums [ i ] % 2 == 0 ) { s -= nums [ i ]; } nums [ i ] += v ; if ( nums [ i ] % 2 == 0 ) { s += nums [ i ]; } ans [ j ] = s ; } return ans ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.