Dada una array arr[] de tamaño N , la tarea es imprimir el recuento mínimo de subconjuntos de igual longitud en los que se puede dividir la array de modo que cada subconjunto contenga solo un único elemento distinto
Ejemplos:
Entrada: arr[] = { 1, 2, 3, 4, 4, 3, 2, 1 }
Salida: 4
Explicación:
La partición posible de la array es { {1, 1}, {2, 2}, {3, 3}, {4, 4} }.
Por lo tanto, la salida requerida es 4.Entrada: arr[] = { 1, 1, 1, 2, 2, 2, 3, 3 }
Salida: 8
Explicación:
La partición posible de la array es { {1}, {1}, {1}, {2} , {2}, {2}, {3}, {3} }.
Por lo tanto, la salida requerida es 8.
Enfoque ingenuo: el enfoque más simple para resolver el problema es almacenar la frecuencia de cada elemento de array distinto , iterar sobre el rango [N, 1] usando la variable i y verificar si la frecuencia de todos los elementos distintos de la array es divisible por yo o no Si se encuentra que es cierto, imprima el valor de (N / i) .
Complejidad Temporal: O(N 2 ).
Espacio Auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar el concepto de GCD . Siga los pasos a continuación para resolver el problema:
- Inicialice un mapa , digamos freq , para almacenar la frecuencia de cada elemento distinto de la array.
- Inicialice una variable, digamos, FreqGCD , para almacenar el GCD de frecuencia de cada elemento distinto de la array.
- Recorra el mapa para encontrar el valor de FreqGCD .
- Finalmente, imprima el valor de (N) % FreqGCD .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum count of subsets
// by partitioning the array with given conditions
int CntOfSubsetsByPartitioning(int arr[], int N)
{
// Store frequency of each
// distinct element of the array
unordered_map<int, int> freq;
// Traverse the array
for (int i = 0; i < N; i++) {
// Update frequency
// of arr[i]
freq[arr[i]]++;
}
// Stores GCD of frequency of
// each distinct element of the array
int freqGCD = 0;
for (auto i : freq) {
// Update freqGCD
freqGCD = __gcd(freqGCD, i.second);
}
return (N) / freqGCD;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 4, 3, 2, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << CntOfSubsetsByPartitioning(arr, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to find the minimum count of subsets
// by partitioning the array with given conditions
static int CntOfSubsetsByPartitioning(int arr[], int N)
{
// Store frequency of each
// distinct element of the array
HashMap<Integer,Integer> freq = new HashMap<>();
// Traverse the array
for (int i = 0; i < N; i++) {
// Update frequency
// of arr[i]
if(freq.containsKey(arr[i])){
freq.put(arr[i], freq.get(arr[i])+1);
}
else{
freq.put(arr[i], 1);
}
}
// Stores GCD of frequency of
// each distinct element of the array
int freqGCD = 0;
for (Map.Entry<Integer,Integer> i : freq.entrySet()) {
// Update freqGCD
freqGCD = __gcd(freqGCD, i.getValue());
}
return (N) / freqGCD;
}
// Recursive function to return gcd of a and b
static int __gcd(int a, int b)
{
return b == 0? a:__gcd(b, a % b);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4, 4, 3, 2, 1 };
int N = arr.length;
System.out.print(CntOfSubsetsByPartitioning(arr, N));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to implement
# the above approach
from math import gcd
# Function to find the minimum count
# of subsets by partitioning the array
# with given conditions
def CntOfSubsetsByPartitioning(arr, N):
# Store frequency of each
# distinct element of the array
freq = {}
# Traverse the array
for i in range(N):
# Update frequency
# of arr[i]
freq[arr[i]] = freq.get(arr[i], 0) + 1
# Stores GCD of frequency of
# each distinct element of the array
freqGCD = 0
for i in freq:
# Update freqGCD
freqGCD = gcd(freqGCD, freq[i])
return (N) // freqGCD
# Driver Code
if __name__ == '__main__':
arr = [ 1, 2, 3, 4, 4, 3, 2, 1 ]
N = len(arr)
print(CntOfSubsetsByPartitioning(arr, N))
# This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the minimum count of subsets
// by partitioning the array with given conditions
static int CntOfSubsetsByPartitioning(int []arr, int N)
{
// Store frequency of each
// distinct element of the array
Dictionary<int,int> freq = new Dictionary<int,int>();
// Traverse the array
for (int i = 0; i < N; i++) {
// Update frequency
// of arr[i]
if(freq.ContainsKey(arr[i])){
freq[arr[i]] = freq[arr[i]]+1;
}
else{
freq.Add(arr[i], 1);
}
}
// Stores GCD of frequency of
// each distinct element of the array
int freqGCD = 0;
foreach (KeyValuePair<int,int> i in freq) {
// Update freqGCD
freqGCD = __gcd(freqGCD, i.Value);
}
return (N) / freqGCD;
}
// Recursive function to return gcd of a and b
static int __gcd(int a, int b)
{
return b == 0? a:__gcd(b, a % b);
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, 2, 3, 4, 4, 3, 2, 1 };
int N = arr.Length;
Console.Write(CntOfSubsetsByPartitioning(arr, N));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to find the minimum count of subsets
// by partitioning the array with given conditions
function CntOfSubsetsByPartitioning(arr, N)
{
// Store frequency of each
// distinct element of the array
var freq = {};
// Traverse the array
for(var i = 0; i < N; i++)
{
// Update frequency
// of arr[i]
if (freq.hasOwnProperty(arr[i]))
{
freq[arr[i]] = freq[arr[i]] + 1;
}
else
{
freq[arr[i]] = 1;
}
}
// Stores GCD of frequency of
// each distinct element of the array
var freqGCD = 0;
for(const [key, value] of Object.entries(freq))
{
// Update freqGCD
freqGCD = __gcd(freqGCD, value);
}
return parseInt(N / freqGCD);
}
// Recursive function to return gcd of a and b
function __gcd(a, b)
{
return b == 0 ? a : __gcd(b, a % b);
}
// Driver Code
var arr = [ 1, 2, 3, 4, 4, 3, 2, 1 ];
var N = arr.length;
document.write(CntOfSubsetsByPartitioning(arr, N));
// This code is contributed by rdtank
</script>
4
Complejidad de tiempo: O(N * log(M)), donde M es el elemento más pequeño de la array
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por indrashish74 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA