Dada una array arr de números naturales hasta n , encuentre el tamaño máximo para el cual la array arr se puede dividir en dos arrays de igual tamaño, de modo que la primera array contenga todos los mismos elementos mientras que la segunda array contenga todos los elementos distintos.
Ejemplos:
Entrada: n = 8, arr[] ={7, 3, 7, 1, 7, 7}
Salida:
El tamaño máximo es: 3
arr1[] ={7, 7, 7}
arr2[] ={1, 3, 7}
Explicación:
es posible construir dos arrays de tamaño 3.
La primera array es [7, 7, 7] y la segunda array es [1, 3, 7].
Entrada: n = 7, arr[] ={1, 2, 1, 5, 1, 6, 7, 2}
Salida:
El tamaño máximo es: 3
arr1[] ={1, 1, 1}
arr2[] ={ 2, 5, 6}
Enfoque:
para resolver el problema mencionado anteriormente, la idea principal es usar hashing para encontrar la frecuencia de cada elemento presente en la array.
- Encuentre el elemento con la máxima frecuencia presente en la array arr[] usando el vector hash v.
- Encuentre el total de elementos únicos presentes en el arreglo arr[].
- Hay dos casos para el elemento con frecuencia máxima: el elemento de frecuencia máxima irá a la primera array, luego los tamaños de la array son como máximo diff1 – 1 y max1 correspondientemente. De lo contrario, al menos un elemento de frecuencia máxima va a la segunda array y los tamaños son como máximo diff1 y max1 ? 1 correspondientemente. Luego encuentre el tamaño máximo en el que se puede dividir la array como max(min(diff1 ? 1, max1), min(diff1, max1 ? 1)) .
- Encuentre la primera array de elementos similares usando max_size y elemento con frecuencia máxima max1.
- Encuentre la segunda array de elementos únicos usando max_size y hash vector v.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the max-size to which
// an array can be divided into 2 equal parts
// such that one part contains unique elements
// while another contains similar elements
#include <bits/stdc++.h>
using namespace std;
// Function to find the max-size to which an array
// can be divided into 2 equal parts
void Solve(int arr[], int size, int n)
{
vector<int> v(n + 1);
// Vector to find the frequency of
// each element of array
for (int i = 0; i < size; i++)
v[arr[i]]++;
// Find the maximum frequency
// element present in array arr[]
int max1 = (max_element(v.begin(), v.end())
- v.begin());
// Find total unique elements
// present in array arr[]
int diff1 = n + 1 - count(v.begin(), v.end(), 0);
// Find the Max-Size to which
// an array arr[] can be splitted
int max_size = max(min(v[max1] - 1, diff1),
min(v[max1], diff1 - 1));
cout << "Maximum size is :" << max_size << "\n";
// Find the first array
// containing same elements
cout << "The First Array Is : \n";
for (int i = 0; i < max_size; i++) {
cout << max1 << " ";
v[max1] -= 1;
}
cout << "\n";
// Find the second array
// containing unique elements
cout << "The Second Array Is : \n";
for (int i = 0; i < (n + 1); i++) {
if (v[i] > 0) {
cout << i << " ";
max_size--;
}
if (max_size < 1)
break;
}
cout << "\n";
}
// Driver code
int main()
{
// initialise n
int n = 7;
// array declaration
int arr[] = { 1, 2, 1, 5, 1, 6, 7, 2 };
// size of array
int size = sizeof(arr) / sizeof(arr[0]);
Solve(arr, size, n);
return 0;
}
Java
// Java program to find the
// max-size to which an array
// can be divided into 2 equal parts
// such that one part contains unique
// elements while another contains
// similar elements
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to find the max-size to
// which an array can be divided into
// 2 equal parts
static void Solve(int arr[],
int size, int n)
{
int[] v = new int[n + 1];
// Array to find the frequency of
// each element of array
for (int i = 0; i < size; i++)
v[arr[i]]++;
// Find the index maximum frequency
// element present in array arr[]
int max1 = -1, mx = -1;
for (int i = 0; i < v.length; i++)
{
if (v[i] > mx)
{
mx = v[i];
max1 = i;
}
}
// Find total unique elements
// present in array arr[]
int cnt = 0;
for (int i : v)
{
if (i == 0)
++cnt;
}
int diff1 = n + 1 - cnt;
// Find the Max-Size to which
// an array arr[] can be splitted
int max_size = Math.max(Math.min(v[max1] - 1,
diff1),
Math.min(v[max1],
diff1 - 1));
System.out.println("Maximum size is: " +
max_size);
// Find the first array
// containing same elements
System.out.println("First Array is");
for (int i = 0; i < max_size; i++)
{
System.out.print(max1 + " ");
v[max1] -= 1;
}
System.out.println();
// Find the second array
// containing unique elements
System.out.println("The Second Array Is :");
for (int i = 0; i < (n + 1); i++)
{
if (v[i] > 0)
{
System.out.print(i + " ");
max_size--;
}
if (max_size < 1)
break;
}
System.out.println();
}
// Driver Code
public static void main(String[] args)
{
// initialise n
int n = 7;
// array declaration
int arr[] = new int[] {1, 2, 1, 5,
1, 6, 7, 2};
// size of array
int size = arr.length;
Solve(arr, size, n);
}
}
// This code is contributed by Sri_srajit
Python3
# Python3 program to find the max-size to which
# an array can be divided into 2 equal parts
# such that one part contains unique elements
# while another contains similar elements
# Function to find the max-size to which an
# array can be divided into 2 equal parts
def Solve(arr, size, n):
v = [0] * (n + 1);
# Vector to find the frequency of
# each element of list
for i in range(size):
v[arr[i]] += 1
# Find the maximum frequency
# element present in list arr
max1 = max(set(arr), key = v.count)
# Find total unique elements
# present in list arr
diff1 = n + 1 - v.count(0)
# Find the Max-Size to which
# an array arr[] can be splitted
max_size = max(min(v[max1] - 1, diff1),
min(v[max1], diff1 - 1))
print("Maximum size is :", max_size)
# Find the first array
# containing same elements
print("The First Array Is : ")
for i in range(max_size):
print(max1, end = " ")
v[max1] -= 1
print()
# Find the second array
# containing unique elements
print("The Second Array Is : ")
for i in range(n + 1):
if (v[i] > 0):
print(i, end = " ")
max_size -= 1
if (max_size < 1):
break
print()
# Driver code
if __name__ == "__main__":
# Initialise n
n = 7
# Array declaration
arr = [ 1, 2, 1, 5, 1, 6, 7, 2 ]
# Size of array
size = len(arr)
Solve(arr, size, n)
# This code is contributed by chitranayal
C#
// C# program to find the max-size
// to which an array can be divided
// into 2 equal parts such that one
// part contains unique elements
// while another contains similar
// elements
using System;
class GFG{
// Function to find the max-size to
// which an array can be divided into
// 2 equal parts
static void Solve(int []arr,
int size, int n)
{
int[] v = new int[n + 1];
// Array to find the frequency of
// each element of array
for(int i = 0; i < size; i++)
v[arr[i]]++;
// Find the index maximum frequency
// element present in array arr[]
int max1 = -1, mx = -1;
for(int i = 0; i < v.Length; i++)
{
if (v[i] > mx)
{
mx = v[i];
max1 = i;
}
}
// Find total unique elements
// present in array arr[]
int cnt = 0;
foreach(int i in v)
{
if (i == 0)
++cnt;
}
int diff1 = n + 1 - cnt;
// Find the Max-Size to which
// an array arr[] can be splitted
int max_size = Math.Max(Math.Min(v[max1] - 1,
diff1),
Math.Min(v[max1],
diff1 - 1));
Console.Write("Maximum size is :" +
max_size + "\n");
// Find the first array
// containing same elements
Console.Write("The First Array Is :\n");
for(int i = 0; i < max_size; i++)
{
Console.Write(max1 + " ");
v[max1] -= 1;
}
Console.Write("\n");
// Find the second array
// containing unique elements
Console.Write("The Second Array Is :\n");
for(int i = 0; i < (n + 1); i++)
{
if (v[i] > 0)
{
Console.Write(i + " ");
max_size--;
}
if (max_size < 1)
break;
}
Console.Write("\n");
}
// Driver Code
public static void Main(string[] args)
{
// Initialise n
int n = 7;
// Array declaration
int []arr = new int[] { 1, 2, 1, 5,
1, 6, 7, 2 };
// Size of array
int size = arr.Length;
Solve(arr, size, n);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript program to find the
// max-size to which an array
// can be divided into 2 equal parts
// such that one part contains unique
// elements while another contains
// similar elements
// Function to find the max-size to
// which an array can be divided into
// 2 equal parts
function Solve(arr, size, n)
{
let v = Array.from({length: n+1}, (_, i) => 0);
// Array to find the frequency of
// each element of array
for (let i = 0; i < size; i++)
v[arr[i]]++;
// Find the index maximum frequency
// element present in array arr[]
let max1 = -1, mx = -1;
for (let i = 0; i < v.length; i++)
{
if (v[i] > mx)
{
mx = v[i];
max1 = i;
}
}
// Find total unique elements
// present in array arr[]
let cnt = 0;
for (let i in v)
{
if (i == 0)
++cnt;
}
let diff1 = n + 1 - cnt;
// Find the Max-Size to which
// an array arr[] can be splitted
let max_size = Math.max(Math.min(v[max1] - 1,
diff1),
Math.min(v[max1],
diff1 - 1));
document.write("Maximum size is: " +
max_size + "<br/>");
// Find the first array
// containing same elements
document.write("First Array is" + "<br/>");
for (let i = 0; i < max_size; i++)
{
document.write(max1 + " ");
v[max1] -= 1;
}
document.write("<br/>");
// Find the second array
// containing unique elements
document.write("The Second Array Is :" + "<br/>");
for (let i = 0; i < (n + 1); i++)
{
if (v[i] > 0)
{
document.write(i + " ");
max_size--;
}
if (max_size < 1)
break;
}
document.write("<br/>");
}
// Driver code
// initialise n
let n = 7;
// array declaration
let arr = [1, 2, 1, 5,
1, 6, 7, 2];
// size of array
let size = arr.length;
Solve(arr, size, n);
// This code is contributed by code_hunt.
</script>
Producción:
Maximum size is :3 The First Array Is : 1 1 1 The Second Array Is : 2 5 6
Complejidad de tiempo : O(N)
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por epistler_999 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA