Dada una array arr[] de enteros y una array q[] de consultas.
Para la i -ésima consulta, index = q[i][0] y value = q[i][1] . La tarea es para cada consulta, actualizar arr[índice] = arr[índice] + valor y luego devolver la suma de todos los elementos pares de la array.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4}, q[] = {{0, 1}, {1, -3}, {0, -4}, {3, 2}}
Salida: 8 6 2 4
Al principio, la array es {1, 2, 3, 4}.
Después de agregar 1 a arr[0], la array se convierte en {2, 2, 3, 4} y la suma de los valores pares es 2 + 2 + 4 = 8.
Agregue -3 a arr[1], arr[] = { 2, -1, 3, 4} y la suma de los valores pares es 2 + 4 = 6.
Agregue -4 a arr[0], arr[] = {-2, -1, 3, 4} y la suma de los valores pares son -2 + 4 = 2.
Sumar 2 a arr[3], arr[] = {-2, -1, 3, 6} y la suma de los valores pares es -2 + 6 = 4.Entrada: arr[] = {1, 2, 2, 2}, q[] = {{0, 1}, {1, 1}}
Salida: 8 6
Enfoque ingenuo: para cada consulta, actualice el valor en la array y calcule la suma de todos los valores pares de la array.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
8 6 2 4
Complejidad temporal: O(n 2 )
Espacio Auxiliar: O(n)
Enfoque eficiente:
- Calcule la suma de los valores pares en arr[]
- Ahora, si el valor de arr[] en el índice dado es par, es decir, arr[index] % 2 = 0, entonces reste arr[index] de la suma.
- Agregue el valor dado a arr[índice], es decir, arr[índice] = arr[índice] + valor.
- Ahora verifique nuevamente si el valor de arr[index] es par, si es así, agregue arr[index] a la suma.
- Imprime el valor de sum para cada consulta.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
8 6 2 4
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por Chandan_Agrawal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA