Dada una array arr[] en la que inicialmente todos los elementos son 0 y otra array Q[][] que contiene K consultas donde cada consulta representa un rango [L, R] , la tarea es agregar 1 a cada subarreglo donde se define cada subarreglo por el rango [L, R] y devuelve la suma de todos los elementos únicos .
Nota: La indexación basada en uno se usa en la array Q[][] para indicar los rangos.
Ejemplos:
Entrada: arr[] = { 0, 0, 0, 0, 0, 0 }, Q[][2] = {{1, 3}, {4, 6}, {3, 4}, {3, 3 }}
Salida: 6
Explicación:
Inicialmente, la array es arr[] = { 0, 0, 0, 0, 0, 0 }.
Consulta 1: arr[] = { 1, 1, 1, 0, 0, 0 }.
Consulta 2: arr[] = { 1, 1, 1, 1, 1, 1 }.
Consulta 3: arr[] = { 1, 1, 2, 2, 1, 1 }.
Consulta 4: arr[] = { 1, 1, 3, 2, 1, 1 }.
Por lo tanto, los elementos únicos son {1, 3, 2}. Por lo tanto suma = 1 + 3 + 2 = 6.
Entrada: arr[] = { 0, 0, 0, 0, 0, 0, 0, 0 }, Q[][2] = {{1, 4}, { 5, 5}, {7, 8}, {8, 8}}
Salida: 3
Explicación:
Inicialmente, la array es arr[] = { 0, 0, 0, 0, 0, 0, 0, 0 }.
Después de procesar todas las consultas, arr[] = { 1, 1, 1, 1, 1, 0, 1, 2 }.
Por lo tanto, los elementos únicos son {1, 0, 2}. Así suma = 1 + 0 + 2 = 3.
Enfoque: La idea es incrementar el valor en 1 y disminuir la array en 1 en el índice L y R+1 respectivamente para procesar cada consulta. Luego, calcule la suma del prefijo de la array para encontrar la array final después de las consultas Q. Como se explica en este artículo. Finalmente, calcule la suma de los elementos únicos con la ayuda del mapa hash .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// sum of all unique elements of
// the array after Q queries
#include <bits/stdc++.h>
using namespace std;
// Function to find the sum of
// unique elements after Q Query
int uniqueSum(int A[], int R[][2],
int N, int M)
{
// Updating the array after
// processing each query
for (int i = 0; i < M; ++i) {
int l = R[i][0], r = R[i][1] + 1;
// Making it to 0-indexing
l--;
r--;
A[l]++;
if (r < N)
A[r]--;
}
// Iterating over the array
// to get the final array
for (int i = 1; i < N; ++i) {
A[i] += A[i - 1];
}
// Variable to store the sum
int ans = 0;
// Hash to maintain previously
// occurred elements
unordered_set<int> s;
// Loop to find the maximum sum
for (int i = 0; i < N; ++i) {
if (s.find(A[i]) == s.end())
ans += A[i];
s.insert(A[i]);
}
return ans;
}
// Driver code
int main()
{
int A[] = { 0, 0, 0, 0, 0, 0 };
int R[][2]
= { { 1, 3 }, { 4, 6 },
{ 3, 4 }, { 3, 3 } };
int N = sizeof(A) / sizeof(A[0]);
int M = sizeof(R) / sizeof(R[0]);
cout << uniqueSum(A, R, N, M);
return 0;
}
Java
// Java implementation to find the
// sum of all unique elements of
// the array after Q queries
import java.util.*;
class GFG{
// Function to find the sum of
// unique elements after Q Query
static int uniqueSum(int A[], int R[][],
int N, int M)
{
// Updating the array after
// processing each query
for (int i = 0; i < M; ++i)
{
int l = R[i][0], r = R[i][1] + 1;
// Making it to 0-indexing
l--;
r--;
A[l]++;
if (r < N)
A[r]--;
}
// Iterating over the array
// to get the final array
for (int i = 1; i < N; ++i)
{
A[i] += A[i - 1];
}
// Variable to store the sum
int ans = 0;
// Hash to maintain previously
// occurred elements
HashSet<Integer> s = new HashSet<Integer>();
// Loop to find the maximum sum
for (int i = 0; i < N; ++i)
{
if (!s.contains(A[i]))
ans += A[i];
s.add(A[i]);
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int A[] = { 0, 0, 0, 0, 0, 0 };
int R[][] = { { 1, 3 }, { 4, 6 },
{ 3, 4 }, { 3, 3 } };
int N = A.length;
int M = R.length;
System.out.print(uniqueSum(A, R, N, M));
}
}
// This code is contributed by gauravrajput1
Python 3
# Python implementation to find the
# sum of all unique elements of
# the array after Q queries
# Function to find the sum of
# unique elements after Q Query
def uniqueSum(A, R, N, M) :
# Updating the array after
# processing each query
for i in range(0, M) :
l = R[i][0]
r = R[i][1] + 1
# Making it to 0-indexing
l -= 1
r -= 1
A[l] += 1
if (r < N) :
A[r] -= 1
# Iterating over the array
# to get the final array
for i in range(1, N) :
A[i] += A[i - 1]
# Variable to store the sum
ans = 0
# Hash to maintain previously
# occurred elements
s = {chr}
# Loop to find the maximum sum
for i in range(0, N) :
if (A[i] not in s) :
ans += A[i]
s.add(A[i])
return ans
# Driver code
A = [ 0, 0, 0, 0, 0, 0 ]
R = [ [ 1, 3 ], [ 4, 6 ],
[ 3, 4 ], [ 3, 3 ] ]
N = len(A)
M = len(R)
print(uniqueSum(A, R, N, M))
# This code is contributed by Sanjit_Prasad
C#
// C# implementation to find the
// sum of all unique elements of
// the array after Q queries
using System;
using System.Collections.Generic;
class GFG{
// Function to find the sum of
// unique elements after Q Query
static int uniqueSum(int []A, int [,]R,
int N, int M)
{
// Updating the array after
// processing each query
for(int i = 0; i < M; ++i)
{
int l = R[i, 0], r = R[i, 1] + 1;
// Making it to 0-indexing
l--;
r--;
A[l]++;
if (r < N)
A[r]--;
}
// Iterating over the array
// to get the readonly array
for(int i = 1; i < N; ++i)
{
A[i] += A[i - 1];
}
// Variable to store the sum
int ans = 0;
// Hash to maintain previously
// occurred elements
HashSet<int> s = new HashSet<int>();
// Loop to find the maximum sum
for(int i = 0; i < N; ++i)
{
if (!s.Contains(A[i]))
ans += A[i];
s.Add(A[i]);
}
return ans;
}
// Driver code
public static void Main(String[] args)
{
int []A = { 0, 0, 0, 0, 0, 0 };
int [,]R = { { 1, 3 }, { 4, 6 },
{ 3, 4 }, { 3, 3 } };
int N = A.Length;
int M = R.GetLength(0);
Console.Write(uniqueSum(A, R, N, M));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript implementation to find the
// sum of all unique elements of
// the array after Q queries
// Function to find the sum of
// unique elements after Q Query
function uniqueSum(A, R, N, M)
{
// Updating the array after
// processing each query
for (let i = 0; i < M; ++i)
{
let l = R[i][0], r = R[i][1] + 1;
// Making it to 0-indexing
l--;
r--;
A[l]++;
if (r < N)
A[r]--;
}
// Iterating over the array
// to get the final array
for (let i = 1; i < N; ++i)
{
A[i] += A[i - 1];
}
// Variable to store the sum
let ans = 0;
// Hash to maintain previously
// occurred elements
let s = new Set();
// Loop to find the maximum sum
for (let i = 0; i < N; ++i)
{
if (!s.has(A[i]))
ans += A[i];
s.add(A[i]);
}
return ans;
}
// Driver code
let A = [ 0, 0, 0, 0, 0, 0 ];
let R = [[ 1, 3 ], [ 4, 6 ],
[ 3, 4 ], [ 3, 3 ]];
let N = A.length;
let M = R.length;
document.write(uniqueSum(A, R, N, M));
// This code is contributed by code_hunt.
</script>
6
Complejidad temporal: O(M + N)
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA