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 indexint 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 queryvoid 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 codeint 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 approachclass 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 indexdef 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 querydef 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 codeA = [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 approachusing 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 indexfunction 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 queryfunction 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 codevar 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(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 queryvoid 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 codeint 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 approachclass 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 approachusing 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 queryfunction 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 queryfunction 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 codevar 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
