Dada una array A[] de longitud N , la tarea es encontrar el tamaño mínimo de la array después de seleccionar y eliminar pares de elementos distintos cualquier cantidad de veces.
Ejemplos:
Entrada: A[] = {1, 7, 7, 4, 4, 4}, N = 6
Salida: 0
Explicación: A partir de la array se pueden formar 3 pares que contienen elementos distintos. Por lo tanto, no queda ningún elemento en la array.Entrada: A[] = {25, 25}, N = 2
Salida: 2
Explicación: No se pueden formar pares que contengan elementos distintos a partir de la array. Por lo tanto, quedan 2 elementos en la array.
Solución: siga los pasos a continuación para resolver este problema:
- Cree un mapa, digamos mp para almacenar la frecuencia de cada elemento en la array. Sea m la frecuencia máxima de cualquier elemento .
- Si la longitud de la array es par:
- Note que si m es menor o igual que ( N /2), entonces cada elemento puede formar un par con otro. Por lo tanto, salida 0.
- De lo contrario, el tamaño mínimo de la array, es decir, el número de elementos que quedan sin un par viene dado por:
- Si la longitud de la array es impar:
- Observe que si m es mayor o igual que ( N /2), entonces 1 elemento siempre quedará sin ningún par. Por lo tanto, la salida 1.
- De lo contrario, el tamaño mínimo de la array estará nuevamente dado por (2* m – N ).
A continuación se muestra la implementación del código anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum size of
// of the array after performing a set of
// operations
int minSize(int N, int A[])
{
// Map to store the frequency of each
// element of the array
map<int, int> mpp;
// Stores the maximum frequency of an
// element
int m = 0;
// Loop to find the maximum frequency of
// an element
for (int i = 0; i < N; ++i) {
// Increment the frequency
mpp[A[i]]++;
// Stores the maximum frequency
m = max(mpp[A[i]], m);
}
// If N is even
if (N % 2 == 0) {
// If m is less than or equal to N/2
if (m <= N / 2) {
return 0;
}
else {
return (2 * m) - N;
}
}
else {
// If m is less than or equal to N/2
if (m <= N / 2) {
return 1;
}
else {
return (2 * m) - N;
}
}
}
// Driver Code
int main()
{
// Given input
int N = 6;
int A[N] = { 1, 7, 7, 4, 4, 4 };
// Function Call
cout << minSize(N, A);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find the minimum size of
// of the array after performing a set of
// operations
static int minSize(int N, int[] A)
{
// Map to store the frequency of each
// element of the array
HashMap<Integer, Integer> mpp
= new HashMap<Integer, Integer>();
// Stores the maximum frequency of an
// element
int m = 0;
// Loop to find the maximum frequency of
// an element
for (int i = 0; i < N; ++i) {
// Increment the frequency
if (mpp.containsKey(A[i])) {
mpp.put(A[i], mpp.get(A[i]) + 1);
}
else {
mpp.put(A[i], 1);
}
// Stores the maximum frequency
m = Math.max(mpp.get(A[i]), m);
}
// If N is even
if (N % 2 == 0) {
// If m is less than or equal to N/2
if (m <= N / 2) {
return 0;
}
else {
return (2 * m) - N;
}
}
else {
// If m is less than or equal to N/2
if (m <= N / 2) {
return 1;
}
else {
return (2 * m) - N;
}
}
}
// Driver Code
public static void main(String[] args)
{
// Given input
int N = 6;
int[] A = { 1, 7, 7, 4, 4, 4 };
// Function Call
System.out.println(minSize(N, A));
}
}
// This code is contributed by ukasp.
Python3
# Python program for the above approach
# Function to find the minimum size of
# of the array after performing a set of
# operations
def minSize(N, A):
# Map to store the frequency of each
# element of the array
mpp = {}
# Stores the maximum frequency of an
# element
m = 0
# Loop to find the maximum frequency of
# an element
for i in range(N):
if A[i] not in mpp:
mpp[A[i]]=0
# Increment the frequency
mpp[A[i]]+=1
# Stores the maximum frequency
m = max(mpp[A[i]], m)
# If N is even
if (N % 2 == 0):
# If m is less than or equal to N/2
if (m <= N / 2):
return 0
else:
return (2 * m) - N
else:
# If m is less than or equal to N/2
if (m <= N / 2):
return 1
else:
return (2 * m) - N
# Driver Code
# Given input
N = 6
A = [1, 7, 7, 4, 4, 4]
# Function Call
print(minSize(N, A))
# This code is contributed by Shubham Singh
C#
// C# program for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
// Function to find the minimum size of
// of the array after performing a set of
// operations
static int minSize(int N, int []A)
{
// Map to store the frequency of each
// element of the array
Dictionary<int, int> mpp =
new Dictionary<int, int>();
// Stores the maximum frequency of an
// element
int m = 0;
// Loop to find the maximum frequency of
// an element
for (int i = 0; i < N; ++i) {
// Increment the frequency
if (mpp.ContainsKey(A[i]))
{
mpp[A[i]] = mpp[A[i]] + 1;
}
else
{
mpp.Add(A[i], 1);
}
// Stores the maximum frequency
m = Math.Max(mpp[A[i]], m);
}
// If N is even
if (N % 2 == 0) {
// If m is less than or equal to N/2
if (m <= N / 2) {
return 0;
}
else {
return (2 * m) - N;
}
}
else {
// If m is less than or equal to N/2
if (m <= N / 2) {
return 1;
}
else {
return (2 * m) - N;
}
}
}
// Driver Code
public static void Main()
{
// Given input
int N = 6;
int []A = { 1, 7, 7, 4, 4, 4 };
// Function Call
Console.Write(minSize(N, A));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Function to find the minimum size of
// of the array after performing a set of
// operations
function minSize(N, A) {
// Map to store the frequency of each
// element of the array
let mpp = new Map();
// Stores the maximum frequency of an
// element
let m = 0;
// Loop to find the maximum frequency of
// an element
for (let i = 0; i < N; ++i) {
// Increment the frequency
if (!mpp.has(A[i]))
mpp.set(A[i], 1);
else
mpp.set(A[i], mpp.get(A[i]) + 1)
// Stores the maximum frequency
m = Math.max(mpp.get(A[i]), m);
}
// If N is even
if (N % 2 == 0) {
// If m is less than or equal to N/2
if (m <= Math.floor(N / 2)) {
return 0;
}
else {
return (2 * m) - N;
}
}
else {
// If m is less than or equal to N/2
if (m <= Math.floor(N / 2)) {
return 1;
}
else {
return (2 * m) - N;
}
}
}
// Driver Code
// Given input
let N = 6;
let A = [1, 7, 7, 4, 4, 4]
// Function Call
document.write(minSize(N, A));
// This code is contributed by Potta Lokesh
</script>
Producción:
0
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por anusha00466 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA