Dada una array A[] de N enteros no negativos y un entero K . Cada vez, puede hacer las siguientes dos operaciones
- Encuentre el promedio de MAX y MEX (redondeado al entero mayor más cercano) de la array.
- Inserte el promedio calculado en la array.
Después de realizar la operación anterior K veces, encuentre la cantidad de elementos únicos presentes en la array.
Nota: MEX es el número entero positivo mínimo que no está presente en la array.
Ejemplos:
Entrada: A = [ 0, 5, 1, 2, 1, 8 ], K=1
Salida: 6
Explicación: En la primera operación, Max = 8 y MEX = 3 .
Entonces el promedio es ( 8 + 3 ) / 2 = 5.5 = 6 (redondeado hacia arriba).
Inserte 6 en la array, luego Array se convierte en: [ 0, 5, 1, 2, 1, 8, 6 ].
Entonces, el recuento de elementos únicos es 6 .Entrada: A = [ 0, 1, 2 ], K = 2
Salida: 5
Explicación: En la primera operación, Max = 2 y MEX = 3.
Entonces el promedio es ( 2 + 3 ) / 2 = 2.5 = 3 (redondeado hacia arriba).
Agregue 3 en la array, luego la array se convierte en: [ 0, 1, 2, 3 ].
En la segunda operación, nuevamente Max = 3 y MEX = 4, Average = 4.
Entonces agregue 4 en la array. Ahora el Array se convierte en [ 0, 1, 2, 3, 4 ].
Entonces, el recuento de elementos únicos es 5.
Enfoque ingenuo: recorra la array dada K veces, y en cada iteración:
- Averigüe el MAX y MEX en la array.
- Calcular el promedio.
- Inserte ese elemento en la array.
Complejidad temporal: O(N*K)
Espacio auxiliar: O(1)
Enfoque Eficiente: La solución al problema se basa en los siguientes dos casos:
Caso-1 (Cuando Max > MEX): El promedio de Max y MEX siempre estará entre Max y MEX y no habrá cambios en el valor Max o el valor MEX.
Entonces no importa si el promedio se suma una vez o K veces.
Si el promedio es único, el recuento de elementos únicos aumentará en 1; de lo contrario, el recuento único será el mismo.Caso-2 (Cuando Max < MEX): El promedio de Max y MEX siempre será mayor que el Max existente. Entonces, en cada paso, se agregará un nuevo elemento único a la array, es decir, un total de K elementos agregados en K operaciones.
por ejemplo, arr[] = {0, 1, 2} y K = 2.
- En el primer paso Max y MEX son 2 y 3 respectivamente. Entonces se sumará (2+3)/2 = 3. La array será {0, 1, 2, 3}.
- En el segundo paso Max y MEX son 3 y 4 respectivamente. Entonces se sumará (3+4)/2 = 4. La array será {0, 1, 2, 3, 4}. Por lo tanto, se agregarán 2 elementos únicos en 2 operaciones.
Siga los pasos que se mencionan a continuación para resolver el problema:
- Cree una array hash para almacenar los elementos únicos.
- Inserte todos los elementos de array dados en la array hash.
- Calcule Max y MEX para la array dada.
- Si Max es mayor que MEX , calcule el promedio e introdúzcalo en la array hash.
- Si MEX es mayor que Max , simplemente agregue K al conteo de elementos únicos en la array porque, en todas las operaciones K, el elemento único se agrega a la array.
- Devuelve el recuento de los elementos únicos en la array hash.
A continuación se muestra la implementación del enfoque anterior.
C++
//c++ program for Count number Unique element after
//adding average of MEX and MAX in array K times.
#include <bits/stdc++.h>
using namespace std;
int uniqueElement(vector<int>& A, int K)
{
// Hash array
unordered_map<int, int> mp;
int max_no = 0;
// Find out MAX of given Array
for (int i = 0; i < A.size(); i++) {
mp[A[i]]++;
max_no = max(max_no, A[i]);
}
int mex = INT_MIN;
// Find out MEX of given Array
for (int i = 0; i < max_no; i++) {
if (mp.find(i) == mp.end()) {
mex = i;
break;
}
}
if (mex == INT_MIN)
mex = max_no + 1;
// Hash array contains only unique elements
// So number of unique elements in array =
// size of Hash array
int unique = mp.size();
if (K != 0) {
if (max_no > mex) {
// Calculated rounded average of MAX and MEX
int avg = round((float)(max_no + mex) / 2);
// If MAX > MEX and avg in not present
// in array Increment count of unique
//element by one.
if (mp[avg] == 0)
unique++;
}
// If MEX > MAX, for every operation, one
// new unique element is added in array
else {
unique += K;
}
}
return unique;
}
//Driver code
int main()
{
vector<int> A = { 3, 0, 2, 4, 1, 2, 3, 5 };
int K = 3;
cout << uniqueElement(A, K);
return 0;
}
Java
import java.util.*;
import java.io.*;
class GFG{
// Function to find remaining element
public static int uniqueElement(ArrayList<Integer> A, int K){
// Hash array
TreeMap<Integer, Integer> mp = new TreeMap<Integer,Integer>();
int max_no = 0;
// Find out MAX of given Array
for(int i = 0 ; i<A.size() ; i++){
if(mp.containsKey(A.get(i))){
mp.put(A.get(i), mp.get(A.get(i))+1);
}else{
mp.put(A.get(i), 1);
}
max_no = Math.max(max_no, A.get(i));
}
int mex = -1;
// Find out MEX of given Array
for(int i=0 ; i<max_no ; i++){
if(mp.containsKey(i)){
}else{
mex = i;
break;
}
}
if(mex==-1){
mex = max_no+1;
}
// Hash array contains only unique elements
// So number of unique elements in array =
// size of Hash array
int unique = mp.size();
if(K != 0){
if(max_no > mex){
// Calculated rounded average of MAX and MEX
int avg = Math.round((float)(max_no+mex)/2);
// If MAX > MEX and avg in not present
// in array Increment count of unique
//element by one.
if (!mp.containsKey(avg) || mp.get(avg) == 0){
unique++;
}
}
// If MEX > MAX, for every operation, one
// new unique element is added in array
else {
unique += K;
}
}
return unique;
}
// Driver code
public static void main(String args[])
{
// Size of array
ArrayList<Integer> A = new ArrayList<Integer>(
List.of(3, 0, 2, 4, 1, 2, 3, 5)
);
int K = 3;
// Function call
System.out.println(uniqueElement(A, K));
}
}
// This code is contributed by subhamgoyal2014.
Python3
# python3 program for Count number Unique element after
# adding average of MEX and MAX in array K times.
INT_MIN = -2147483647 - 1
def uniqueElement(A, K):
# Hash array
mp = {}
max_no = 0
# Find out MAX of given Array
for i in range(0, len(A)):
mp[A[i]] = mp[A[i]] + 1 if A[i] in mp else 1
max_no = max(max_no, A[i])
mex = INT_MIN
# Find out MEX of given Array
for i in range(0, max_no):
if (not i in mp):
mex = i
break
if (mex == INT_MIN):
mex = max_no + 1
# Hash array contains only unique elements
# So number of unique elements in array =
# size of Hash array
unique = len(mp)
if (K != 0):
if (max_no > mex):
# Calculated rounded average of MAX and MEX
avg = round((max_no + mex) / 2)
# If MAX > MEX and avg in not present
# in array Increment count of unique
# element by one.
if (mp[avg] == 0):
unique += 1
# If MEX > MAX, for every operation, one
# new unique element is added in array
else:
unique += K
return unique
# Driver code
if __name__ == "__main__":
A = [3, 0, 2, 4, 1, 2, 3, 5]
K = 3
print(uniqueElement(A, K))
# This code is contributed by rakeshsahni
C#
// c# program for Count number Unique element after
// adding average of MEX and MAX in array K times.
using System;
using System.Collections.Generic;
class GFG {
static int uniqueElement(int[] A, int K)
{
// Hash array
Dictionary<int, int> mp
= new Dictionary<int, int>();
int max_no = 0;
// Find out MAX of given Array
for (int i = 0; i < A.Length; i++) {
if (mp.ContainsKey(A[i])) {
mp[A[i]] = mp[A[i]] + 1;
}
else {
mp.Add(A[i], 1);
}
max_no = Math.Max(max_no, A[i]);
}
int mex = Int32.MinValue;
// Find out MEX of given Array
for (int i = 0; i < max_no; i++) {
if (!mp.ContainsKey(i)) {
mex = i;
break;
}
}
if (mex == Int32.MinValue)
mex = max_no + 1;
// Hash array contains only unique elements
// So number of unique elements in array =
// size of Hash array
int unique = mp.Count;
if (K != 0) {
if (max_no > mex) {
// Calculated rounded average of MAX and MEX
float temp = (max_no + mex) / 2;
int avg = (int)Math.Round(temp);
// If MAX > MEX and avg in not present
// in array Increment count of unique
// element by one.
if (mp[avg] == 0)
unique++;
}
// If MEX > MAX, for every operation, one
// new unique element is added in array
else {
unique += K;
}
}
return unique;
}
// Driver code
public static void Main()
{
int[] A = { 3, 0, 2, 4, 1, 2, 3, 5 };
int K = 3;
Console.Write(uniqueElement(A, K));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
function uniqueElement(A, K)
{
// Hash array
let mp = new Map();
let max_no = 0;
// Find out MAX of given Array
for (let i = 0; i < A.length; i++) {
if (mp.has(A[i])) {
mp.set(A[i], mp.get(A[i] + 1))
}
else {
mp.set(A[i], 1)
}
max_no = Math.max(max_no, A[i]);
}
let mex = Number.MIN_VALUE;
// Find out MEX of given Array
for (let i = 0; i < max_no; i++) {
if (!mp.has(i)) {
mex = i;
break;
}
}
if (mex == Number.MIN_VALUE)
mex = max_no + 1;
// Hash array contains only unique elements
// So number of unique elements in array =
// size of Hash array
let unique = mp.size;
if (K != 0) {
if (max_no > mex) {
// Calculated rounded average of MAX and MEX
let avg = Math.fround((max_no + mex) / 2);
// If MAX > MEX and avg in not present
// in array Increment count of unique
//element by one.
if (mp.get(avg) == 0)
unique++;
}
// If MEX > MAX, for every operation, one
// new unique element is added in array
else {
unique += K;
}
}
return unique;
}
// Driver code
let A = [3, 0, 2, 4, 1, 2, 3, 5];
let K = 3;
document.write(uniqueElement(A, K));
// This code is contributed by Potta Lokesh
</script>
Producción:
9
Complejidad de tiempo: O(N*logN )
Espacio auxiliar: O(N )
Publicación traducida automáticamente
Artículo escrito por khatriharsh281 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA