Dada una array de enteros arr[] y consultas Q , la tarea es encontrar la suma de la array para cada consulta del siguiente tipo:
- Cada consulta contiene 2 enteros X e Y , donde todas las apariciones de X en arr[] deben reemplazarse por Y .
- Después de cada consulta, imprimen la suma de la array.
Ejemplos:
Entrada: arr[] = { 1, 2, 1, 3, 2}, X[] = { 2, 3, 5 }, Y[] = { 3, 1, 2 }
Salida: 11 5 5
Explicación:
Después de la Primera consulta, reemplace 2 con 3, arr[] = { 1, 3, 1, 3, 3 }, Sum = 11.
Después de la segunda consulta, reemplace 3 con 1, arr[] = { 1, 1, 1, 1 , 1 }, Sum = 5.
Después de la tercera consulta, reemplace 5 con 2, arr[] = { 1, 1, 1, 1, 1 }, Sum = 5.Entrada: arr[] = { 12, 22, 11, 11, 2}, X[] = {2, 11, 22}, Y[] = {12, 222, 2}
Salida: 68 490 470
Enfoque ingenuo:
el enfoque más simple para resolver el problema mencionado anteriormente es atravesar la array y reemplazar todas las instancias de X con Y para cada consulta y calcular la suma.
Complejidad de tiempo: O(N * Q)
Enfoque eficiente:
para optimizar el método anterior, siga los pasos que se indican a continuación:
- Calcule previamente y almacene la suma de la array en una variable S y almacene las frecuencias de los elementos de la array en un conteo de mapas .
- Luego, haga lo siguiente para cada consulta:
- Encuentre la frecuencia de X almacenada en el mapa.
- Restar X * cuenta[X] de S .
- Establezca count[Y] = count[X] y luego count[X] = 0 .
- Agregue Y * cuenta[Y] a S .
- Imprime el valor actualizado de S .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the sum
// of the array for the given Q queries
#include <bits/stdc++.h>
using namespace std;
// Function that print the sum of
// the array for Q queries
void sumOfTheArrayForQuery(int* A, int N,
int* X, int* Y,
int Q)
{
int sum = 0;
// Stores the frequencies
// of array elements
unordered_map<int, int> count;
// Calculate the sum of
// the initial array and
// store the frequency of
// each element in map
for (int i = 0; i < N; i++) {
sum += A[i];
count[A[i]]++;
}
// Iterate for all the queries
for (int i = 0; i < Q; i++) {
// Store query values
int x = X[i], y = Y[i];
// Decrement the sum accordingly
sum -= count[X[i]] * X[i];
// Increment the sum accordingly
sum += count[X[i]] * Y[i];
// Set count of Y[i]
count[Y[i]] += count[X[i]];
// Reset count of X[i]
count[X[i]] = 0;
// Print the sum
cout << sum << " ";
}
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 1, 3, 2 };
int X[] = { 2, 3, 5 };
int Y[] = { 3, 1, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
int Q = sizeof(X) / sizeof(X[0]);
// Function call
sumOfTheArrayForQuery(arr, N, X, Y, Q);
return 0;
}
Java
// Java implementation to
// find the sum of the array
// for the given Q queries
import java.util.*;
class GFG{
// Function that print the sum of
// the array for Q queries
public static void sumOfTheArrayForQuery(int[] A, int N,
int[] X, int[] Y,
int Q)
{
int sum = 0;
// Stores the frequencies
// of array elements
// Create an empty hash map
HashMap<Integer,
Integer> count = new HashMap<>();
// Calculate the sum of
// the initial array and
// store the frequency of
// each element in map
for (int i = 0; i < N; i++)
{
sum += A[i];
if (count.containsKey(A[i]))
{
count.replace(A[i],
count.get(A[i]) + 1);
}
else
{
count.put(A[i], 1);
}
}
// Iterate for all the queries
for (int i = 0; i < Q; i++)
{
// Store query values
int x = X[i], y = Y[i];
if(count.containsKey(X[i]))
{
// Decrement the sum accordingly
sum -= count.get(X[i]) * X[i];
// Increment the sum accordingly
sum += count.get(X[i]) * Y[i];
}
// Set count of Y[i]
if(count.containsKey(Y[i]) &&
count.containsKey(X[i]))
{
count.replace(Y[i],
count.get(Y[i]) +
count.get(X[i]));
}
// Reset count of X[i]
if(count.containsKey(X[i]))
{
count.replace(X[i], 0);
}
// Print the sum
System.out.print(sum + " ");
}
}
// Driver code
public static void main(String[] args)
{
int arr[] = {1, 2, 1, 3, 2};
int X[] = {2, 3, 5};
int Y[] = {3, 1, 2};
int N = arr.length;
int Q = X.length;
// Function call
sumOfTheArrayForQuery(arr, N,
X, Y, Q);
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 implementation to find the sum
# of the array for the given Q queries
# Function that print the sum of
# the array for Q queries
def sumOfTheArrayForQuery(A, N, X, Y, Q):
sum = 0
# Stores the frequencies
# of array elements
count = {}
# Calculate the sum of
# the initial array and
# store the frequency of
# each element in map
for i in range(N):
sum += A[i]
if A[i] in count:
count[A[i]] += 1
else:
count[A[i]] = 1
# Iterate for all the queries
for i in range(Q):
# Store query values
x = X[i]
y = Y[i]
if X[i] not in count:
count[X[i]] = 0
if Y[i] not in count:
count[Y[i]] = 0
# Decrement the sum accordingly
sum -= (count[X[i]] * X[i])
# Increment the sum accordingly
sum += count[X[i]] * Y[i]
# Set count of Y[i]
count[Y[i]] += count[X[i]]
# Reset count of X[i]
count[X[i]] = 0
# Print the sum
print(sum, end = " ")
# Driver Code
arr = [ 1, 2, 1, 3, 2, ]
X = [ 2, 3, 5 ]
Y = [ 3, 1, 2 ]
N = len(arr)
Q = len(X)
# Function call
sumOfTheArrayForQuery(arr, N, X, Y, Q)
# This code is contributed by avanitrachhadiya2155
C#
// C# implementation to
// find the sum of the array
// for the given Q queries
using System;
using System.Collections.Generic;
class GFG{
// Function that print the sum of
// the array for Q queries
public static void sumOfTheArrayForQuery(int[] A, int N,
int[] X, int[] Y,
int Q)
{
int sum = 0;
// Stores the frequencies
// of array elements
// Create an empty hash map
Dictionary<int,
int> count = new Dictionary<int,
int>();
// Calculate the sum of
// the initial array and
// store the frequency of
// each element in map
for (int i = 0; i < N; i++)
{
sum += A[i];
if (count.ContainsKey(A[i]))
{
count[A[i]]= count[A[i]] + 1;
}
else
{
count.Add(A[i], 1);
}
}
// Iterate for all the queries
for (int i = 0; i < Q; i++)
{
// Store query values
int x = X[i], y = Y[i];
if(count.ContainsKey(X[i]))
{
// Decrement the sum accordingly
sum -= count[X[i]] * X[i];
// Increment the sum accordingly
sum += count[X[i]] * Y[i];
}
// Set count of Y[i]
if(count.ContainsKey(Y[i]) &&
count.ContainsKey(X[i]))
{
count[Y[i]] = count[Y[i]] +
count[X[i]];
}
// Reset count of X[i]
if(count.ContainsKey(X[i]))
{
count[X[i]] = 0;
}
// Print the sum
Console.Write(sum + " ");
}
}
// Driver code
public static void Main(String[] args)
{
int []arr = {1, 2, 1, 3, 2};
int []X = {2, 3, 5};
int []Y = {3, 1, 2};
int N = arr.Length;
int Q = X.Length;
// Function call
sumOfTheArrayForQuery(arr, N,
X, Y, Q);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript implementation to find the sum
// of the array for the given Q queries
// Function that print the sum of
// the array for Q queries
function sumOfTheArrayForQuery(A, N, X, Y, Q)
{
var sum = 0;
// Stores the frequencies
// of array elements
var count = new Map();
// Calculate the sum of
// the initial array and
// store the frequency of
// each element in map
for (var i = 0; i < N; i++) {
sum += A[i];
if(count.has(A[i]))
count.set(A[i], count.get(A[i])+1)
else
count.set(A[i], 1)
}
// Iterate for all the queries
for (var i = 0; i < Q; i++) {
// Store query values
var x = X[i], y = Y[i];
if(count.has(X[i]))
{
// Decrement the sum accordingly
sum -= count.get(X[i]) * X[i];
// Increment the sum accordingly
sum += count.get(X[i]) * Y[i];
}
if(count.has(Y[i]))
{
// Set count of Y[i]
count.set(Y[i], count.get(Y[i]) + count.get(X[i]));
}
// Reset count of X[i]
count.set(X[i] , 0);
// Print the sum
document.write( sum + " ");
}
}
// Driver Code
var arr = [1, 2, 1, 3, 2];
var X = [2, 3, 5 ];
var Y = [3, 1, 2 ];
var N = arr.length;
var Q = X.length;
// Function call
sumOfTheArrayForQuery(arr, N, X, Y, Q);
</script>
Producción:
11 5 5
Complejidad temporal: O(N), ya que cada consulta tiene una complejidad computacional de O(1).
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rupesh_rao y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA