Se le da una array de n elementos. Debe crear subconjuntos a partir de la array de modo que ningún subconjunto contenga elementos duplicados. Averigüe el número mínimo de subconjuntos posibles.
Ejemplos:
Input : arr[] = {1, 2, 3, 4}
Output :1
Explanation : A single subset can contains all
values and all values are distinct
Input : arr[] = {1, 2, 3, 3}
Output : 2
Explanation : We need to create two subsets
{1, 2, 3} and {3} [or {1, 3} and {2, 3}] such
that both subsets have distinct elements.
Básicamente necesitamos encontrar el elemento más frecuente en la array. El resultado es igual a la frecuencia del elemento más frecuente.
Una solución simple es ejecutar dos bucles anidados para contar la frecuencia de cada elemento y devolver la frecuencia del elemento más frecuente. La complejidad temporal de esta solución es O(n 2 ).
Una mejor solución es ordenar primero la array y luego comenzar a contar el número de repeticiones de los elementos de manera iterativa, ya que todas las repeticiones de cualquier número se encuentran junto al número en sí. Con este método, puede encontrar la frecuencia o repetición máxima simplemente recorriendo la array ordenada. Este enfoque costará O(nlogn) complejidad de tiempo
Implementación:
C++
// A sorting based solution to find the
// minimum number of subsets of a set
// such that every subset contains distinct
// elements.
#include <bits/stdc++.h>
using namespace std;
// Function to count subsets such that all
// subsets have distinct elements.
int subset(int ar[], int n)
{
// Take input and initialize res = 0
int res = 0;
// Sort the array
sort(ar, ar + n);
// Traverse the input array and
// find maximum frequency
for (int i = 0; i < n; i++) {
int count = 1;
// For each number find its repetition / frequency
for (; i < n - 1; i++) {
if (ar[i] == ar[i + 1])
count++;
else
break;
}
// Update res
res = max(res, count);
}
return res;
}
// Driver code
int main()
{
int arr[] = { 5, 6, 9, 3, 4, 3, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << subset(arr, n);
return 0;
}
Java
// A sorting based solution to find the
// minimum number of subsets of a set
// such that every subset contains distinct
// elements.
import java.util.*;
import java.lang.*;
public class GfG{
// Function to count subsets such that all
// subsets have distinct elements.
public static int subset(int ar[], int n)
{
// Take input and initialize res = 0
int res = 0;
// Sort the array
Arrays.sort(ar);
// Traverse the input array and
// find maximum frequency
for (int i = 0; i < n; i++) {
int count = 1;
// For each number find its repetition / frequency
for (; i < n - 1; i++) {
if (ar[i] == ar[i + 1])
count++;
else
break;
}
// Update res
res = Math.max(res, count);
}
return res;
}
// Driver function
public static void main(String argc[])
{
int arr[] = { 5, 6, 9, 3, 4, 3, 4 };
int n = 7;
System.out.println(subset(arr, n));
}
}
/* This code is contributed by Sagar Shukla */
Python3
# A sorting based solution to find the # minimum number of subsets of a set # such that every subset contains distinct # elements. # function to count subsets such that all # subsets have distinct elements. def subset(ar, n): # take input and initialize res = 0 res = 0 # sort the array ar.sort() # traverse the input array and # find maximum frequency for i in range(0, n) : count = 1 # for each number find its repetition / frequency for i in range(n - 1): if ar[i] == ar[i + 1]: count+=1 else: break # update res res = max(res, count) return res # Driver code ar = [ 5, 6, 9, 3, 4, 3, 4 ] n = len(ar) print(subset(ar, n)) # This code is contributed by # Smitha Dinesh Semwal
C#
// A sorting based solution to find the
// minimum number of subsets of a set
// such that every subset contains distinct
// elements.
using System;
public class GfG {
// Function to count subsets such that all
// subsets have distinct elements.
public static int subset(int []ar, int n)
{
// Take input and initialize res = 0
int res = 0;
// Sort the array
Array.Sort(ar);
// Traverse the input array and
// find maximum frequency
for (int i = 0; i < n; i++) {
int count = 1;
// For each number find its
// repetition / frequency
for ( ; i < n - 1; i++) {
if (ar[i] == ar[i + 1])
count++;
else
break;
}
// Update res
res = Math.Max(res, count);
}
return res;
}
// Driver function
public static void Main()
{
int []arr = { 5, 6, 9, 3, 4, 3, 4 };
int n = 7;
Console.WriteLine(subset(arr, n));
}
}
/* This code is contributed by Vt_m */
PHP
<?php
// A sorting based solution to find the
// minimum number of subsets of a set
// such that every subset contains distinct
// elements.
// Function to count subsets such that all
// subsets have distinct elements.
function subset($ar, $n)
{
// Take input and initialize res = 0
$res = 0;
// Sort the array
sort($ar);
// Traverse the input array and
// find maximum frequency
for ($i = 0; $i < $n; $i++)
{
$count = 1;
// For each number find its
// repetition / frequency
for (; $i < $n - 1; $i++)
{
if ($ar[$i] == $ar[$i + 1])
$count++;
else
break;
}
// Update res
$res = max($res, $count);
}
return $res;
}
// Driver code
$arr = array( 5, 6, 9, 3, 4, 3, 4 );
$n = sizeof($arr);
echo subset($arr, $n);
// This code is contributed
// by Sach_Code
?>
Javascript
<script>
// JavaScript program sorting based solution to find the
// minimum number of subsets of a set
// such that every subset contains distinct
// Function to count subsets such that all
// subsets have distinct elements.
function subset(ar, n)
{
// Take input and initialize res = 0
let res = 0;
// Sort the array
ar.sort();
// Traverse the input array and
// find maximum frequency
for (let i = 0; i < n; i++)
{
let count = 1;
// For each number find its repetition / frequency
for (; i < n - 1; i++)
{
if (ar[i] == ar[i + 1])
count++;
else
break;
}
// Update res
res = Math.max(res, count);
}
return res;
}
// Driver Code
let arr = [ 5, 6, 9, 3, 4, 3, 4 ];
let n = 7;
document.write(subset(arr, n));
// This code is contributed by chinmoy1997pal.
</script>
Producción
2
Complejidad de Tiempo: O(n 2 )
Espacio Auxiliar: O(1)
Una solución eficiente es usar hashing. Contamos las frecuencias de todos los elementos en una tabla hash. Finalmente devolvemos la clave con el valor máximo en la tabla hash.
Implementación:
C++
// A hashing based solution to find the
// minimum number of subsets of a set
// such that every subset contains distinct
// elements.
#include <bits/stdc++.h>
using namespace std;
// Function to count subsets such that all
// subsets have distinct elements.
int subset(int arr[], int n)
{
// Traverse the input array and
// store frequencies of elements
unordered_map<int, int> mp;
for (int i = 0; i < n; i++)
mp[arr[i]]++;
// Find the maximum value in map.
int res = 0;
for (auto x : mp)
res = max(res, x.second);
return res;
}
// Driver code
int main()
{
int arr[] = { 5, 6, 9, 3, 4, 3, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << subset(arr, n);
return 0;
}
Java
import java.util.HashMap;
import java.util.Map;
// A hashing based solution to find the
// minimum number of subsets of a set
// such that every subset contains distinct
// elements.
class GFG
{
// Function to count subsets such that all
// subsets have distinct elements.
static int subset(int arr[], int n)
{
// Traverse the input array and
// store frequencies of elements
HashMap<Integer, Integer> mp = new HashMap<>();
for (int i = 0; i < n; i++)
mp.put(arr[i],mp.get(arr[i]) == null?1:mp.get(arr[i])+1);
// Find the maximum value in map.
int res = 0;
for (Map.Entry<Integer,Integer> entry : mp.entrySet())
res = Math.max(res, entry.getValue());
return res;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 5, 6, 9, 3, 4, 3, 4 };
int n = arr.length;
System.out.println( subset(arr, n));
}
}
// This code is contributed by Rajput-Ji
Python3
# A hashing based solution to find the
# minimum number of subsets of a set such
# that every subset contains distinct
# elements.
# Function to count subsets such that
# all subsets have distinct elements.
def subset(arr, n):
# Traverse the input array and
# store frequencies of elements
mp = {i:0 for i in range(10)}
for i in range(n):
mp[arr[i]] += 1
# Find the maximum value in map.
res = 0
for key, value in mp.items():
res = max(res, value)
return res
# Driver code
if __name__ == '__main__':
arr = [5, 6, 9, 3, 4, 3, 4]
n = len(arr)
print(subset(arr, n))
# This code is contributed by
# Surendra_Gangwar
C#
// A hashing based solution to find the
// minimum number of subsets of a set
// such that every subset contains distinct
// elements.
using System;
using System.Collections.Generic;
class GFG
{
// Function to count subsets such that all
// subsets have distinct elements.
static int subset(int []arr, int n)
{
// Traverse the input array and
// store frequencies of elements
Dictionary<int,
int> mp = new Dictionary<int,
int>();
for (int i = 0 ; i < n; i++)
{
if(mp.ContainsKey(arr[i]))
{
var val = mp[arr[i]];
mp.Remove(arr[i]);
mp.Add(arr[i], val + 1);
}
else
{
mp.Add(arr[i], 1);
}
}
// Find the maximum value in map.
int res = 0;
foreach(KeyValuePair<int, int> entry in mp)
res = Math.Max(res, entry.Value);
return res;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 5, 6, 9, 3, 4, 3, 4 };
int n = arr.Length;
Console.WriteLine(subset(arr, n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// A hashing based solution to find the
// minimum number of subsets of a set
// such that every subset contains distinct
// elements.
// Function to count subsets such that all
// subsets have distinct elements.
function subset(arr, n) {
// Traverse the input array and
// store frequencies of elements
var mp = {};
for (var i = 0; i < n; i++) {
if (mp.hasOwnProperty(arr[i])) {
var val = mp[arr[i]];
delete mp[arr[i]];
mp[arr[i]] = val + 1;
} else {
mp[arr[i]] = 1;
}
}
// Find the maximum value in map.
var res = 0;
for (const [key, value] of Object.entries(mp)) {
res = Math.max(res, value);
}
return res;
}
// Driver code
var arr = [5, 6, 9, 3, 4, 3, 4];
var n = arr.length;
document.write(subset(arr, n));
// This code is contributed by rdtank.
</script>
Producción
2
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA