Dada una array arr[] de enteros y una array de consultas , la tarea es encontrar la suma del producto de cada número y su frecuencia en el rango dado [L, R] donde cada rango se proporciona en la array de consultas.
Ejemplos:
Entrada: arr[] = [1, 2, 1], Consultas: [{1, 2}, {1, 3}]
Salida: [3, 4]
Explicación:
Para consulta [1, 2], freq[1] = 1, frecuencia[2] = 1, respuesta = (1 * frecuencia[1]) + (2 * frecuencia[2]) => respuesta = (1 * 1 + 2 * 1) = 3
Para consulta [1, 3 ], frecuencia[1] = 2, frecuencia[2] = 1; respuesta = (1 * frecuencia[1]) + (2 * frecuencia[2]) => respuesta = (1 * 2) + (2 * 1) = 4Entrada: arr[] = [1, 1, 2, 2, 1, 3, 1, 1], Consultas: [{2, 7}, {1, 6}]
Salida: [10, 10]
Explicación:
Para consulta (2, 7), frecuencia[1] = 3, frecuencia[2] = 2, frecuencia[3] = 3;
respuesta = (1 * frecuencia[1]) + (2 * frecuencia[2] ) + (3 * frecuencia[3])
respuesta = (1 * 3) + (2 * 2) + (3 * 1) = 10
Enfoque ingenuo:
para resolver el problema mencionado anteriormente, el método ingenuo es iterar sobre el subarreglo dado en la consulta. Mantenga un mapa para la frecuencia de cada número en el subarreglo e itere sobre el mapa y calcule la respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find
// sum of product of every number
// and square of its frequency
// in the given range
#include <bits/stdc++.h>
using namespace std;
// Function to solve queries
void answerQueries(
int arr[], int n,
vector<pair<int, int> >& queries)
{
for (int i = 0; i < queries.size(); i++) {
// Calculating answer
// for every query
int ans = 0;
// The end points
// of the ith query
int l = queries[i].first - 1;
int r = queries[i].second - 1;
// map for storing frequency
map<int, int> freq;
for (int j = l; j <= r; j++) {
// Iterating over the given
// subarray and storing
// frequency in a map
// Incrementing the frequency
freq[arr[j]]++;
}
// Iterating over map to find answer
for (auto& i : freq) {
// adding the contribution
// of ith number
ans += (i.first
* i.second);
}
// print answer
cout << ans << endl;
}
}
// Driver code
int main()
{
int arr[] = { 1, 2, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
vector<pair<int, int> > queries
= { { 1, 2 },
{ 1, 3 } };
answerQueries(arr, n, queries);
}
Java
// Java program to find sum of
// product of every number and
// square of its frequency in
// the given range
import java.util.*;
class GFG{
// Function to solve queries
public static void answerQueries(int[] arr,
int n,
int[][] queries)
{
for(int i = 0; i < queries.length; i++)
{
// Calculating answer
// for every query
int ans = 0;
// The end points
// of the ith query
int l = queries[i][0] - 1;
int r = queries[i][1] - 1;
// Hashmap for storing frequency
Map<Integer,
Integer> freq = new HashMap<>();
for(int j = l; j < r + 1; j++)
{
// Iterating over the given
// subarray and storing
// frequency in a map
// Incrementing the frequency
freq.put(arr[j],
freq.getOrDefault(arr[j], 0) + 1);
}
for(int k: freq.keySet())
{
// Adding the contribution
// of ith number
ans += k * freq.get(k);
}
// Print answer
System.out.println(ans);
}
}
// Driver code
public static void main(String args[] )
{
int[] arr = { 1, 2, 1 };
int n = arr.length;
int[][] queries = { { 1, 2 },
{ 1, 3 } };
// Calling function
answerQueries(arr, n, queries);
}
}
// This code contributed by dadi madhav
Python3
# Python3 implementation to find # sum of product of every number # and square of its frequency # in the given range # Function to solve queries def answerQueries(arr, n, queries): for i in range(len(queries)): # Calculating answer # for every query ans = 0 # The end points # of the ith query l = queries[i][0] - 1 r = queries[i][1] - 1 # Map for storing frequency freq = dict() for j in range(l, r + 1): # Iterating over the given # subarray and storing # frequency in a map # Incrementing the frequency freq[arr[j]] = freq.get(arr[j], 0) + 1 # Iterating over map to find answer for i in freq: # Adding the contribution # of ith number ans += (i * freq[i]) # Print answer print(ans) # Driver code if __name__ == '__main__': arr = [ 1, 2, 1 ] n = len(arr) queries = [ [ 1, 2 ], [ 1, 3 ] ] answerQueries(arr, n, queries) # This code is contributed by mohit kumar 29
C#
// C# program to find sum of
// product of every number and
// square of its frequency in
// the given range
using System;
using System.Collections.Generic;
class GFG{
// Function to solve queries
public static void answerQueries(int[] arr, int n,
int[,] queries)
{
for(int i = 0; i < queries.GetLength(0); i++)
{
// Calculating answer
// for every query
int ans = 0;
// The end points
// of the ith query
int l = queries[i, 0] - 1;
int r = queries[i, 1] - 1;
// Hashmap for storing frequency
Dictionary<int,
int> freq = new Dictionary<int,
int>();
for(int j = l; j < r+ 1; j++)
{
// Iterating over the given
// subarray and storing
// frequency in a map
// Incrementing the frequency
freq[arr[j]] = freq.GetValueOrDefault(arr[j], 0) + 1;
}
foreach(int k in freq.Keys)
{
// Adding the contribution
// of ith number
ans += k * freq[k];
}
// Print answer
Console.WriteLine(ans);
}
}
// Driver code
static public void Main()
{
int[] arr = { 1, 2, 1 };
int n = arr.Length;
int[,] queries = { { 1, 2 }, { 1, 3 } };
// Calling function
answerQueries(arr, n, queries);
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// Javascript implementation to find
// sum of product of every number
// and square of its frequency
// in the given range
// Function to solve queries
function answerQueries(arr, n, queries)
{
for(var i = 0; i < queries.length; i++)
{
// Calculating answer
// for every query
var ans = 0;
// The end points
// of the ith query
var l = queries[i][0] - 1;
var r = queries[i][1] - 1;
// map for storing frequency
var freq = new Map();
for(var j = l; j <= r; j++)
{
// Iterating over the given
// subarray and storing
// frequency in a map
// Incrementing the frequency
if (freq.has(arr[j]))
freq.set(arr[j], freq.get(arr[j]) + 1)
else
freq.set(arr[j], 1)
}
// Iterating over map to find answer
freq.forEach((value, key) => {
// Adding the contribution
// of ith number
ans += (key * value);
});
// Print answer
document.write(ans + "<br>");
}
}
// Driver code
var arr = [ 1, 2, 1 ];
var n = arr.length;
var queries = [ [ 1, 2 ],
[ 1, 3 ] ];
answerQueries(arr, n, queries);
// This code is contributed by itsok
</script>
Producción:
3 4
Complejidad de Tiempo: O(Q * N)
Complejidad de Espacio Auxiliar: O(N)
Enfoque eficiente:
para optimizar el método anterior, intentaremos implementar el problema utilizando el algoritmo de Mo.
- Ordene las consultas primero según su bloque de
tamaño usando un comparador personalizado y también almacene los índices de cada consulta en un mapa para imprimir en orden. - Ahora, mantendremos los dos punteros L y R que iteraremos sobre la array para responder a las consultas. A medida que movemos los punteros, si agregamos algún número en nuestro rango, primero eliminaremos la contribución de su frecuencia anterior de la respuesta, luego incrementaremos la frecuencia y finalmente agregaremos la contribución de la nueva frecuencia en la respuesta.
- Y si quitamos algún elemento del rango, haremos lo mismo, quitamos la contribución de la frecuencia existente de este número, decrementamos la frecuencia, añadimos la contribución de su nueva frecuencia.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find sum
// of product of every number
// and square of its frequency
// in the given range
#include <bits/stdc++.h>
using namespace std;
// Stores frequency
const int N = 1e5 + 5;
// Frequency array
vector<int> freq(N);
int sq;
// Function for comparator
bool comparator(
pair<int, int>& a,
pair<int, int>& b)
{
// comparator for sorting
// according to the which query
// lies in the which block;
if (a.first / sq != b.first / sq)
return a.first < b.first;
// if same block,
// return which query end first
return a.second < b.second;
}
// Function to add numbers in range
void add(int x, int& ans, int arr[])
{
// removing contribution of
// old frequency from answer
ans -= arr[x]
* freq[arr[x]];
// incrementing the frequency
freq[arr[x]]++;
// adding contribution of
// new frequency to answer
ans += arr[x]
* freq[arr[x]];
}
void remove(int x, int& ans, int arr[])
{
// removing contribution of
// old frequency from answer
ans -= arr[x]
* freq[arr[x]];
// Decrement the frequency
freq[arr[x]]--;
// adding contribution of
// new frequency to answer
ans += arr[x]
* freq[arr[x]];
}
// Function to answer the queries
void answerQueries(
int arr[], int n,
vector<pair<int, int> >& queries)
{
sq = sqrt(n) + 1;
vector<int> answer(
int(queries.size()));
// map for storing the
// index of each query
map<pair<int, int>, int> idx;
// Store the index of queries
for (int i = 0; i < queries.size(); i++)
idx[queries[i]] = i;
// Sort the queries
sort(queries.begin(),
queries.end(),
comparator);
int ans = 0;
// pointers for iterating
// over the array
int x = 0, y = -1;
for (auto& i : queries) {
// iterating over all
// the queries
int l = i.first - 1, r = i.second - 1;
int id = idx[i];
while (x > l) {
// decrementing the left
// pointer and adding the
// xth number's contribution
x--;
add(x, ans, arr);
}
while (y < r) {
// incrementing the right
// pointer and adding the
// yth number's contribution
y++;
add(y, ans, arr);
}
while (x < l) {
// incrementing the left pointer
// and removing the
// xth number's contribution
remove(x, ans, arr);
x++;
}
while (y > r) {
// decrementing the right
// pointer and removing the
// yth number's contribution
remove(y, ans, arr);
y--;
}
answer[id] = ans;
}
// printing the answer of queries
for (int i = 0; i < queries.size(); i++)
cout << answer[i] << endl;
}
// Driver Code
int main()
{
int arr[] = { 1, 1, 2, 2, 1, 3, 1, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
vector<pair<int, int> > queries
= { { 2, 7 },
{ 1, 6 } };
answerQueries(arr, n, queries);
}
Producción:
10 10
Complejidad de tiempo: O(N * sqrt{N})
Complejidad de espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por insiderpants y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA