Sum of even values and update queries on an array
Given an array arr[] of integers and an array q[] of queries.
For the ith 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> |
8 6 2 4
Time Complexity: O(n2)
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> |
8 6 2 4
Time Complexity: O(n)
Auxiliary Space: O(n)
Contact Us