Minimice la suma del conteo de elementos únicos en Array después de dividir en [1, N] subconjuntos

Dada una array arr[] de longitud N , la tarea es encontrar el número mínimo de elementos únicos posibles en total cuando la array se divide en K subconjuntos (para todos los K en el rango [1, N] ), es decir, la suma de la cuenta de elementos únicos presentes en cada subconjunto después de dividir la array dada en K subconjuntos.

Ejemplos:

Entrada: arr[] = { 2, 3, 3}
Salida: {2, 2, 3}
Explicación:  
K = 1: {2, 2, 3}
Hay dos elementos distintos en la array anterior = {2, 3}
cuando la array se divide en 1 subarreglo

K = 2: {2, 2}, { 3 }
Hay un tipo de elemento en el primer arreglo y para el segundo subarreglo, 
por lo que la suma del conteo de únicos es 1+1 = 2. 
El arreglo también se puede dividir en 2 subarreglos como sigue {2, 3}, {2} pero entonces
el conteo de elementos únicos será 2 y 1 y la suma será 2+1 = 3 que no es el mínimo.

K = 3: {2}, {2}, {3}
Elementos únicos en el primer subarreglo = 1
Elementos únicos en el segundo subarreglo = 1
Elementos únicos en el tercer subarreglo = 1

Entonces capacidades totales = 1+1+1 = 3

Entrada: arr[] = { 3, 1, 2, 2, 2, 4}
Salida: {4, 4, 4, 4, 5, 6}
Explicación:
K = 1: {1, 2, 2, 2, 4 , 3}
Hay 4 tipos de elementos = { 1, 2, 3, 4}
Entonces, para k = 1, la suma requerida es = 4

K = 2: {2, 2, 2, 4, 3}, {1}
Hay 3 tipos de elementos en el primer subarreglo = {2, 3, 4} 
Entonces los elementos únicos en este subarreglo son 3
Solo hay un tipo de elementos en el segundo subarreglo = { 1}
Entonces los elementos únicos en este subarreglo son 1
Entonces para k = 2, cuenta mínima total = 3+1 = 4

K = 3: {2, 2, 2, 3}, {1}, {4}
Para k = 3, cuenta mínima total = 2+1+1 = 4

K = 4: {2, 2, 2}, {1}, {4}, {3}
Para k = 4, recuento mínimo total = 1+1+1+1 = 4

K = 5: {2, 2}, {1}, {2}, {4}, {3}
Para k = 5, recuento mínimo total = 2+1+1+1+1 = 5

K = 6: {1}, {2}, {2}, {2}, {4}, {3}
Para k = 6, recuento mínimo total = 1+1+1+1+1+1 = 6
cada uno el subarreglo contiene elementos únicos.

Planteamiento: El problema se puede resolver sobre la base de la siguiente idea:

Para minimizar el recuento de elementos únicos en cada subconjunto, agrupe los elementos con los mismos valores en un subconjunto.

Consulte la siguiente ilustración para una mejor comprensión.

Ilustración:

Considere la array arr[] = {2, 2, 3}
Número total de elementos únicos = 2 (2 y 3)

Para dividirlo en k = 1 partes:
        => No puede haber menos de 2 elementos únicos en total.
        => Divídalo en subconjuntos {2, 2, 3} .
        => El recuento total de elementos únicos es 2

Por dividirlo en k = 2 partes:
        => No puede haber menos de 2 elementos únicos en total.
        => Divídalo en subconjuntos {2, 2} y {3} .
        => El recuento total de elementos únicos es 1 + 1 = 2

Para dividirlo en k = 3 partes:
        => Para minimizar el recuento total de elementos únicos, rompa solo un grupo de elementos similares y mantenga los demás intactos.
        => Aquí solo había un grupo con todos los elementos similares: {2, 2}.
        => Divide eso en 2 partes: {2}, {2}.
        => Divídalo en subconjuntos {2}, {2} y {3} .
        => El recuento total de elementos únicos es 1 + 1 + 1 = 3

Siga los pasos mencionados a continuación para implementar la idea anterior:

• Calcule la cantidad de elementos distintos  usando hashSet (digamos contar )
• Comience a iterar para k = 1 a N
  • Si k es como máximo el conteo , intente agrupar elementos similares en un subarreglo para minimizar el conteo total de elementos únicos. En este caso, el número total de elementos únicos siempre será igual a contar , ya que el número de elementos únicos no se puede reducir.
  • Si k es mayor que el conteo, habrá un mínimo de k elementos únicos en total en todos los subconjuntos, porque tenemos que romper un grupo de elementos similares cada vez, lo que aumentará el subarreglo y, por lo tanto, también el conteo de elementos únicos totales.
• Imprime el conteo total para cada k,

Debajo de la implementación del enfoque anterior.

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the
// minimum possible number
// of unique elements
void solution(int a[], int n)
{
   
    // To store the unique elements
    set<int> hs;
    for (int i = 0; i < n; i++)
        hs.insert(a[i]);
    int cnt = hs.size();
    for (int i = 1; i <= n; i++) {
        if (i > hs.size()) {
            cnt++;
            cout << cnt << " ";
        }
        else {
            cout << hs.size() << " ";
        }
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 2, 3, 3 };
    int N = sizeof(arr) / sizeof(arr[0]);
    solution(arr, N);
}
 
// This code is contributed by Taranpreet

// Java implementation of above approach
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to count the
    // minimum possible number
    // of unique elements
    public static void solution(int[] a,
                                int n)
    {
        // To store the unique elements
        HashSet<Integer> hs = new HashSet<>();
        for (int i : a)
            hs.add(i);
        int cnt = hs.size();
        for (int i = 1; i <= n; i++) {
            if (i > hs.size()) {
                cnt++;
                System.out.print(cnt + " ");
            }
            else {
                System.out.print(hs.size()
                                 + " ");
            }
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { 2, 3, 3 };
        int N = arr.length;
        solution(arr, N);
    }
}

# Python implementation of above approach
 
# Function to count the
# minimum possible number
# of unique elements
def solution(a, n):
 
    # To store the unique elements
    hs = set()
    for i in range(0, n):
        hs.add(a[i])
    cnt = len(hs)
 
    for i in range(1, n + 1):
        if (i > len(hs)):
            cnt += 1
            print(cnt)
 
        else:
            print(len(hs))
 
# Driver Code
arr = [2, 3, 3]
N = len(arr)
solution(arr, N)
 
# This code is contributed by Samim Hossain Mondal.

// C# implementation of above approach
using System;
using System.Collections.Generic;
 
public class GFG{
 
  // Function to count the
  // minimum possible number
  // of unique elements
  static void solution(int[] a,
                       int n)
  {
    // To store the unique elements
    HashSet<int> hs = new HashSet<int>();       
    foreach(int i in a)
    {
      hs.Add(i);
    }
    int cnt = hs.Count;
    for (int i = 1; i <= n; i++) {
      if (i > hs.Count) {
        cnt++;
        Console.Write(cnt + " ");
      }
      else {
        Console.Write(hs.Count
                      + " ");
      }
    }
  }
 
  // Driver Code
  static public void Main (){
 
    int[] arr = { 2, 3, 3 };
    int N = arr.Length;
    solution(arr, N);
  }
}
 
// This code is contributed by hrithikgarg03188.

<script>
       // JavaScript code for the above approach
 
   // Function to count the
   // minimum possible number
   // of unique elements
   function solution( a, n)
   {
       // To store the unique elements
       let hs = new Set();
       for (let i of a)
           hs.add(i);
       let cnt = hs.size;
       for (let i = 1; i <= n; i++) {
           if (i > hs.size) {
               cnt++;
               document.write(cnt + " ");
           }
           else {
               document.write(hs.size
                                + " ");
           }
       }
   }
 
   // Driver Code
       let arr = [ 2, 3, 3 ];
       let N = arr.length;
       solution(arr, N);
    
    // This code is contributed by Potta Lokesh
   </script>

2 2 3 

Complejidad temporal: O(N)
Espacio auxiliar: O(N)