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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sum of Even Numbers After Queries

Number: 1027

Difficulty: Medium

Paid? No

Companies: Indeed

Problem Description

Given an integer array nums and an array of queries where each query is in the form [val, index], the task is to update the element at nums[index] by adding val and then return the sum of all even numbers in the updated nums. This process is repeated for each query and the output is an array where each element is the even sum after processing the corresponding query.

Key Insights

  • Instead of recalculating the sum of even numbers from scratch after each update, maintain a running sum of even numbers.
  • Before updating an element, check if it is even; if yes, remove its value from the running even sum.
  • After updating, if the new value is even, add it to the running even sum.
  • This approach minimizes the cost of recalculating the sum after every query.

Space and Time Complexity

Time Complexity: O(N + Q) where N is the length of nums and Q is the number of queries, since we compute the initial even sum in O(N) and each query is handled in O(1). Space Complexity: O(1) additional space (apart from the output array) as we only keep track of a few variables.

Solution

The solution uses a simulation strategy with a running even sum variable. Initially, compute the sum of all even numbers in the array. For each query:

  1. Check if the current number at the target index is even; if it is, subtract it from the even sum.
  2. Update the number at the target index by adding the given value.
  3. Check if the updated number is even; if it is, add it to the even sum.
  4. Append the current even sum to the result array. This approach leverages constant-time updates per query, making it efficient.

Code Solutions

# Python solution for "Sum of Even Numbers After Queries"

def sumEvenAfterQueries(nums, queries):
    # Calculate initial sum of even numbers in nums
    even_sum = sum(x for x in nums if x % 2 == 0)
    results = []  # List to store the sum after each query
    
    # Process each query
    for value, index in queries:
        # If the current number at given index is even, remove it from even_sum
        if nums[index] % 2 == 0:
            even_sum -= nums[index]
        
        # Update the value at the index
        nums[index] += value
        
        # If the updated number is even, add it to even_sum
        if nums[index] % 2 == 0:
            even_sum += nums[index]
        
        # Append the current even sum after the query to results list
        results.append(even_sum)
    
    return results

# Example usage:
nums = [1, 2, 3, 4]
queries = [[1, 0], [-3, 1], [-4, 0], [2, 3]]
result = sumEvenAfterQueries(nums, queries)
print(result)  # Output: [8, 6, 2, 4]
← Back to All Questions