We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sum of Even Numbers After Queries

Difficulty: Medium

Problem Description

You are given an integer array nums and an array queries where queries[i] = [val_i, index_i]. For each query i, first, apply nums[index_i] = nums[index_i] + val_i, 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.

Key Insights

  • We need to efficiently update values in the array and calculate the sum of even numbers after each update.
  • Each query involves two operations: updating a specific index and calculating the sum of even numbers.
  • Keeping track of the current sum of even numbers can help optimize the solution.

Space and Time Complexity

Time Complexity: O(n + q), where n is the length of nums and q is the number of queries. Each query involves an update and at most O(1) operations to maintain the sum of even numbers. Space Complexity: O(1), since we are using only a fixed amount of extra space.

Solution

We can maintain a running sum of even numbers in the array. For each query, we update the specified index and check if the new value is even or if it changes the parity of the old value. If the value is even, we add it to the sum; if it becomes odd, we subtract it from the sum. This allows us to quickly return the sum of even numbers after each query without recalculating the entire sum.

Code Solutions

def sumEvenAfterQueries(nums, queries):
    # Calculate initial sum of even numbers
    even_sum = sum(num for num in nums if num % 2 == 0)
    result = []
    
    for val, index in queries:
        # Update the number at the index
        if nums[index] % 2 == 0:  # If the current number is even
            even_sum -= nums[index]  # Remove it from the sum
        nums[index] += val  # Apply the value
        if nums[index] % 2 == 0:  # Check the new number
            even_sum += nums[index]  # Add it to the sum if it's even
        result.append(even_sum)  # Append the current sum of evens
    
    return result
← Back to All Questions