Sum of even values and update queries on an array

0 0 11 minutes read

Given an array arr[] of integers and an array q[] of queries.
For the i^th query, index = q[i][0] and value = q[i][1]. The task is for every query, update arr[index] = arr[index] + value and then return the sum of all the even elements from the array.

Examples:

Input: arr[] = {1, 2, 3, 4}, q[] = {{0, 1}, {1, -3}, {0, -4}, {3, 2}}
Output: 8 6 2 4
At the beginning, the array is {1, 2, 3, 4}.
After adding 1 to arr[0], the array becomes {2, 2, 3, 4} and the sum of even values is 2 + 2 + 4 = 8.
Add -3 to arr[1], arr[] = {2, -1, 3, 4} and the sum of even values is 2 + 4 = 6.
Add -4 to arr[0], arr[] = {-2, -1, 3, 4} and the sum of even values is -2 + 4 = 2.
Adding 2 to arr[3], arr[] = {-2, -1, 3, 6} and the sum of even values is -2 + 6 = 4.

Input: arr[] = {1, 2, 2, 2}, q[] = {{0, 1}, {1, 1}}
Output: 8 6

Naive Approach: For each query, update the value in the array and calculate the sum of all even values from the array.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the sum of even elements
// after updating value at given index
int EvenSum(vector<int>& A, int index, int value)
{
    // Add given value to A[index]
    A[index] = A[index] + value;
 
    // To store the sum of even elements
    int sum = 0;
 
    for (int i = 0; i < A.size(); i++)
 
        // If current element is even
        if (A[i] % 2 == 0)
            sum = sum + A[i];
 
    return sum;
}
 
// Function to print the result for every query
void BalanceArray(vector<int>& A, vector<vector<int> >& Q)
{
 
    // Resultant vector that stores
    // the result for every query
    vector<int> ANS;
 
    int i, sum;
 
    for (i = 0; i < Q.size(); i++) {
 
        int index = Q[i][0];
        int value = Q[i][1];
 
        // Get sum of even elements after updating
        // value at given index
        sum = EvenSum(A, index, value);
 
        // Store sum for each query
        ANS.push_back(sum);
    }
 
    // Print the result for every query
    for (i = 0; i < ANS.size(); i++)
        cout << ANS[i] << " ";
}
 
// Driver code
int main()
{
    vector<int> A = { 1, 2, 3, 4 };
    vector<vector<int> > Q = { { 0, 1 },
                               { 1, -3 },
                               { 0, -4 },
                               { 3, 2 } };
    BalanceArray(A, Q);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
    // Function to return the sum of even elements
    // after updating value at given index
    static int EvenSum(int [] A, int index, int value)
    {
        // Add given value to A[index]
        A[index] = A[index] + value;
     
        // To store the sum of even elements
        int sum = 0;
     
        for (int i = 0; i < A.length; i++)
     
            // If current element is even
            if (A[i] % 2 == 0)
                sum = sum + A[i];
     
        return sum;
    }
     
    // Function to print the result for every query
    static void BalanceArray(int [] A, int [][] Q)
    {
     
        // Resultant vector that stores
        // the result for every query
        int [] ANS = new int[Q.length];
        int i, sum;
     
        for (i = 0; i < Q.length; i++) 
        {
     
            int index = Q[i][0];
            int value = Q[i][1];
     
            // Get sum of even elements after updating
            // value at given index
            sum = EvenSum(A, index, value);
     
            // Store sum for each query
            ANS[i] = sum;
        }
     
        // Print the result for every query
        for (i = 0; i < ANS.length; i++)
            System.out.print(ANS[i] + " ");
    }
     
    // Driver code
    public static void main(String []args)
    {
        int [] A = { 1, 2, 3, 4 };
        int [][] Q = { { 0, 1 },
                        { 1, -3 },
                        { 0, -4 },
                        { 3, 2 } };
        BalanceArray(A, Q);
     
    }
}
 
// This code is contributed by ihritik

Python3

# Python3 implementation of the approach
 
# Function to return the sum of even elements
# after updating value at given index
def EvenSum(A, index, value):
     
    # Add given value to A[index]
    A[index] = A[index] + value
 
    # To store the sum of even elements
    sum = 0
 
    for i in A:
 
        # If current element is even
        if (i % 2 == 0):
            sum = sum + i
 
    return sum
 
# Function to print result for every query
def BalanceArray(A,Q):
 
    # Resultant vector that stores
    # the result for every query
    ANS = []
 
    i, sum = 0, 0
 
    for i in range(len(Q)):
 
        index = Q[i][0]
        value = Q[i][1]
 
        # Get sum of even elements after updating
        # value at given index
        sum = EvenSum(A, index, value)
 
        # Store sum for each query
        ANS.append(sum)
 
    # Print the result for every query
    for i in ANS:
        print(i, end = " ")
 
# Driver code
A = [1, 2, 3, 4]
Q = [ [0, 1 ],
    [1, -3],
    [0, -4],
    [3, 2 ] ]
BalanceArray(A, Q)
 
# This code is contributed by mohit kumar 29

C#

// C# implementation of the approach
using System;
public class GFG
{
 
  // Function to return the sum of even elements
  // after updating value at given index
  static int EvenSum(int[] A, int index, int value) 
  {
 
    // Add given value to A[index]
    A[index] = A[index] + value;
 
    // To store the sum of even elements
    int sum = 0;
 
    for (int i = 0; i < A.Length; i++)
 
      // If current element is even
      if (A[i] % 2 == 0)
        sum = sum + A[i];
 
    return sum;
  }
 
  // Function to print the result for every query
  static void BalanceArray(int[] A, int[,] Q) {
 
    // Resultant vector that stores
    // the result for every query
    int[] ANS = new int[Q.GetLength(0)];
    int i, sum;
 
    for (i = 0; i < Q.GetLength(0); i++) {
 
      int index = Q[i,0];
      int value = Q[i,1];
 
      // Get sum of even elements after updating
      // value at given index
      sum = EvenSum(A, index, value);
 
      // Store sum for each query
      ANS[i] = sum;
    }
 
    // Print the result for every query
    for (i = 0; i < ANS.Length; i++)
      Console.Write(ANS[i] + " ");
  }
 
  // Driver code
  public static void Main(String[] args) 
  {
    int[] A = { 1, 2, 3, 4 };
    int[,] Q = { { 0, 1 }, { 1, -3 }, { 0, -4 }, { 3, 2 } };
    BalanceArray(A, Q);
  }
}
 
// This code is contributed by Rajput-Ji.

Javascript

<script>
 
 
// JavaScript implementation of the approach
 
// Function to return the sum of even elements
// after updating value at given index
function EvenSum(A, index, value)
{
    // Add given value to A[index]
    A[index] = A[index] + value;
 
    // To store the sum of even elements
    var sum = 0;
 
    for (var i = 0; i < A.length; i++)
 
        // If current element is even
        if (A[i] % 2 == 0)
            sum = sum + A[i];
 
    return sum;
}
 
// Function to print the result for every query
function BalanceArray(A, Q)
{
 
    // Resultant vector that stores
    // the result for every query
    var ANS = [];
 
    var i, sum;
 
    for (i = 0; i < Q.length; i++) {
 
        var index = Q[i][0];
        var value = Q[i][1];
 
        // Get sum of even elements after updating
        // value at given index
        sum = EvenSum(A, index, value);
 
        // Store sum for each query
        ANS.push(sum);
    }
 
    // Print the result for every query
    for (i = 0; i < ANS.length; i++)
        document.write( ANS[i] + " ");
}
 
// Driver code
var A = [ 1, 2, 3, 4 ];
var Q = [ [ 0, 1 ],
          [ 1, -3 ],
          [ 0, -4 ],
          [ 3, 2 ] ];
BalanceArray(A, Q);
 
</script>

Output:

8 6 2 4

Time Complexity: O(n²)

Auxiliary Space: O(n)

Efficient Approach:

Calculate the sum of Even values in arr[]
Now if the value of arr[] at given index is even i.e. arr[index] % 2 = 0 then subtract arr[index] from sum.
Add the given value to arr[index] i.e. arr[index] = arr[index] + value.
Now check again if the value of arr[index] is even, if yes then add arr[index] to the sum.
Print the value of sum for every query.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the result for every query
void BalanceArray(vector<int>& A, vector<vector<int> >& Q)
{
    vector<int> ANS;
 
    int i, sum = 0;
 
    for (i = 0; i < A.size(); i++)
 
        // If current element is even
        if (A[i] % 2 == 0)
            sum = sum + A[i];
 
    for (i = 0; i < Q.size(); i++) {
 
        int index = Q[i][0];
        int value = Q[i][1];
 
        // If element is even then
        // remove it from sum
        if (A[index] % 2 == 0)
            sum = sum - A[index];
 
        A[index] = A[index] + value;
 
        // If the value becomes even after updating
        if (A[index] % 2 == 0)
            sum = sum + A[index];
 
        // Store sum for each query
        ANS.push_back(sum);
    }
 
    // Print the result for every query
    for (i = 0; i < ANS.size(); i++)
        cout << ANS[i] << " ";
}
 
// Driver code
int main()
{
    vector<int> A = { 1, 2, 3, 4 };
    vector<vector<int> > Q = { { 0, 1 },
                               { 1, -3 },
                               { 0, -4 },
                               { 3, 2 } };
    BalanceArray(A, Q);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
    // Function to print the result for every query
    static void BalanceArray(int [] A, int [][] Q)
    {
        int [] ANS = new int [A.length];
     
        int i, sum = 0;
     
        for (i = 0; i < A.length; i++)
     
            // If current element is even
            if (A[i] % 2 == 0)
                sum = sum + A[i];
     
        for (i = 0; i < Q.length; i++)
        {
     
            int index = Q[i][0];
            int value = Q[i][1];
     
            // If element is even then
            // remove it from sum
            if (A[index] % 2 == 0)
                sum = sum - A[index];
     
            A[index] = A[index] + value;
     
            // If the value becomes even after updating
            if (A[index] % 2 == 0)
                sum = sum + A[index];
     
            // Store sum for each query
            ANS[i]= sum;
        }
     
        // Print the result for every query
        for (i = 0; i < ANS.length; i++)
            System.out.print(ANS[i] + " ");
    }
     
    // Driver code
    public static void main(String [] args)
    {
        int [] A = { 1, 2, 3, 4 };
        int [][] Q = { { 0, 1 },
                                { 1, -3 },
                                { 0, -4 },
                                { 3, 2 } };
        BalanceArray(A, Q);
    }
}
 
// This code is contributed by ihritik

Python3

# Python3 implementation of the approach 
 
# Function to print the result for 
# every query 
def BalanceArray(A, Q) : 
     
    ANS = []
    sum = 0
 
    for i in range(len(A)) : 
 
        # If current element is even 
        if (A[i] % 2 == 0) :
            sum += A[i]; 
 
    for i in range(len(Q)) :
 
        index = Q[i][0]; 
        value = Q[i][1]; 
 
        # If element is even then 
        # remove it from sum 
        if (A[index] % 2 == 0) :
            sum -= A[index]; 
 
        A[index] += value; 
 
        # If the value becomes even 
        # after updating 
        if (A[index] % 2 == 0) :
            sum += A[index]; 
 
        # Store sum for each query 
        ANS.append(sum); 
     
 
    # Print the result for every query 
    for i in range(len(ANS)) :
        print(ANS[i], end = " "); 
 
# Driver code 
if __name__ == "__main__" :
 
    A = [ 1, 2, 3, 4 ]; 
    Q = [ [ 0, 1 ], [ 1, -3 ], 
          [ 0, -4 ], [ 3, 2 ]]; 
    BalanceArray(A, Q); 
 
# This code is contributed by Ryuga

C#

// C# implementation of the approach
using System;
 
class GFG
{
    // Function to print the result for every query
    static void BalanceArray(int [] A, int [, ] Q)
    {
        int [] ANS = new int [A.Length];
     
        int i, sum = 0;
     
        for (i = 0; i < A.Length; i++)
     
            // If current element is even
            if (A[i] % 2 == 0)
                sum = sum + A[i];
     
        for (i = 0; i < Q.GetLength(0); i++)
        {
     
            int index = Q[i, 0];
            int value = Q[i, 1];
     
            // If element is even then
            // remove it from sum
            if (A[index] % 2 == 0)
                sum = sum - A[index];
     
            A[index] = A[index] + value;
     
            // If the value becomes even after updating
            if (A[index] % 2 == 0)
                sum = sum + A[index];
     
            // Store sum for each query
            ANS[i]= sum;
        }
     
        // Print the result for every query
        for (i = 0; i < ANS.Length; i++)
            Console.Write(ANS[i] + " ");
    }
     
    // Driver code
    public static void Main()
    {
        int [] A = { 1, 2, 3, 4 };
        int [, ] Q = { { 0, 1 },
                                { 1, -3 },
                                { 0, -4 },
                                { 3, 2 } };
        BalanceArray(A, Q);
    }
}
 
// This code is contributed by ihritik

PHP

<?php
// PHP implementation of the approach
 
// Function to print the result for every query
function BalanceArray($A, &$Q)
{
    $ANS = array();
 
    $sum = 0;
 
    for ($i = 0; $i < count($A); $i++)
 
        // If current element is even
        if ($A[$i] % 2 == 0)
            $sum = $sum + $A[$i];
 
    for ($i = 0; $i < count($Q); $i++) 
    {
        $index = $Q[$i][0];
        $value = $Q[$i][1];
 
        // If element is even then
        // remove it from sum
        if ($A[$index] % 2 == 0)
            $sum = $sum - $A[$index];
 
        $A[$index] = $A[$index] + $value;
 
        // If the value becomes even after updating
        if ($A[$index] % 2 == 0)
            $sum = $sum + $A[$index];
 
        // Store sum for each query
        array_push($ANS,$sum);
    }
 
    // Print the result for every query
    for ($i = 0; $i < count($ANS); $i++)
        echo $ANS[$i] . " ";
}
 
// Driver code
$A = array( 1, 2, 3, 4 );
$Q = array(array( 0, 1 ),
           array( 1, -3 ),
           array( 0, -4 ),
           array( 3, 2 ));
BalanceArray($A, $Q);
 
// This code is contributed by chandan_jnu
?>

Javascript

<script>
 
// JavaScript implementation of the approach
 
// Function to print the result for every query
function BalanceArray(A, Q)
{
    var ANS = [];
 
    var i, sum = 0;
 
    for (i = 0; i < A.length; i++)
 
        // If current element is even
        if (A[i] % 2 == 0)
            sum = sum + A[i];
 
    for (i = 0; i < Q.length; i++) {
 
        var index = Q[i][0];
        var value = Q[i][1];
 
        // If element is even then
        // remove it from sum
        if (A[index] % 2 == 0)
            sum = sum - A[index];
 
        A[index] = A[index] + value;
 
        // If the value becomes even after updating
        if (A[index] % 2 == 0)
            sum = sum + A[index];
 
        // Store sum for each query
        ANS.push(sum);
    }
 
    // Print the result for every query
    for (i = 0; i < ANS.length; i++)
        document.write( ANS[i] + " ");
}
 
// Driver code
var A = [ 1, 2, 3, 4 ];
var Q = [ [ 0, 1 ],
         [ 1, -3 ],
         [ 0, -4 ],
          [ 3, 2 ] ];
BalanceArray(A, Q);
 
</script>

Output:

8 6 2 4

Time Complexity: O(n)
Auxiliary Space: O(n)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!