Compruebe si es posible dividir la array en subconjuntos estrictamente crecientes de tamaño al menos K

Dada una array arr[] de tamaño N y un número entero K , la tarea es verificar si es posible dividir la array en subconjuntos estrictamente crecientes de tamaño al menos K . Si es posible, imprima » Sí «. De lo contrario, escriba “ No ”.

Ejemplos:

Entrada: arr[] = {5, 6, 4, 9, 12}, K = 2
Salida: Sí
Explicación: 
una forma posible de dividir la array en subconjuntos de al menos tamaño 2 es, {arr[2](=4 ), array[0](=5)} y {array[1](=6), array[3](=9), array[4](=12)}

Entrada: arr[] = {5, 7, 7, 7}, K = 2
Salida: No

Enfoque: el problema se puede resolver utilizando Map para almacenar la frecuencia de cada elemento y dividiendo la array en X subconjuntos, donde X es la frecuencia del elemento que aparece el número máximo de veces en la array . Siga los pasos a continuación para resolver el problema:

• Inicialice un mapa , digamos m para almacenar la frecuencia de los elementos y también inicialice una variable mx como 0 para almacenar la frecuencia del elemento máximo que ocurre en la array arr[] .
• Recorra la array arr[] usando la variable i , e incremente m[arr[i]] en 1 y actualice el valor de mx a max(mx, m[arr[i]]) .
• Ahora, si N/mx>= K , imprime » Sí «, ya que es el número máximo de elementos que puede tener un subconjunto.
• De lo contrario, escriba “No ”.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if it is possible
// to split the array into strictly
// increasing subsets of size atleast K
string ifPossible(int arr[], int N, int K)
{
 
    // Map to store frequency of elements
    map<int, int> m;
 
    // Stores the frequency of the maximum
    // occurring element in the array
    int mx = 0;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
        m[arr[i]] += 1;
        mx = max(mx, m[arr[i]]);
    }
    // Stores the minimum count of elements
    // in a subset
    int sz = N / mx;
 
    // If sz is greater than k-1
    if (sz >= K) {
        return "Yes";
    }
    // Otherwise
    else {
 
        return "No";
    }
}
 
// Driver Code
int main()
{
    // Given Input
    int arr[] = { 5, 6, 4, 9, 12 };
    int K = 2;
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    cout << ifPossible(arr, N, K);
    return 0;
}

// Java approach for the above program
import java.util.HashMap;
 
public class GFG
{
 
    // Function to check if it is possible
    // to split the array into strictly
    // increasing subsets of size atleast K
    static String ifPossible(int arr[], int N, int K)
    {
 
        // Map to store frequency of elements
        HashMap<Integer, Integer> m
            = new HashMap<Integer, Integer>();
 
        // Stores the frequency of the maximum
        // occurring element in the array
        int mx = 0;
 
        // Traverse the array
        for (int i = 0; i < N; i++) {
            m.put(arr[i], m.getOrDefault(arr[i], 0) + 1);
            mx = Math.max(mx, m.get(arr[i]));
        }
        // Stores the minimum count of elements
        // in a subset
        int sz = N / mx;
 
        // If sz is greater than k-1
        if (sz >= K) {
            return "Yes";
        }
        // Otherwise
        else {
 
            return "No";
        }
    }
    // Driver code
    public static void main(String[] args)
    {
        // Given Input
        int arr[] = { 5, 6, 4, 9, 12 };
        int K = 2;
        int N = arr.length;
 
        // Function Call
        System.out.println(ifPossible(arr, N, K));
    }
}
 
// This code is contributed by abhinavjain194

# Python3 program for the above approach
 
# Function to check if it is possible
# to split the array into strictly
# increasing subsets of size atleast K
def ifPossible(arr, N, K):
     
    # Map to store frequency of elements
    m = {}
 
    # Stores the frequency of the maximum
    # occurring element in the array
    mx = 0
 
    # Traverse the array
    for i in range(N):
        if arr[i] in m:
            m[arr[i]] += 1
        else:
            m[arr[i]] = 1
             
        mx = max(mx, m[arr[i]])
 
    # Stores the minimum count of elements
    # in a subset
    sz = N // mx
 
    # If sz is greater than k-1
    if (sz >= K):
        return "Yes"
 
    # Otherwise
    else:
        return "No"
 
# Driver Code
if __name__ == '__main__':
     
    # Given Input
    arr = [ 5, 6, 4, 9, 12 ]
    K = 2
    N = len(arr)
 
    # Function Call
    print(ifPossible(arr, N, K))
     
# This code is contributed by bgangwar59

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
// Function to check if it is possible
// to split the array into strictly
// increasing subsets of size atleast K
static string ifPossible(int []arr, int N, int K)
{
 
    // Map to store frequency of elements
    Dictionary<int,int> m = new Dictionary<int,int>();
 
    // Stores the frequency of the maximum
    // occurring element in the array
    int mx = 0;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
        if(m.ContainsKey(arr[i]))
          m[arr[i]] += 1;
        else
          m.Add(arr[i],1);
        mx = Math.Max(mx, m[arr[i]]);
    }
   
    // Stores the minimum count of elements
    // in a subset
    int sz = N / mx;
 
    // If sz is greater than k-1
    if (sz >= K) {
        return "Yes";
    }
   
    // Otherwise
    else {
 
        return "No";
    }
}
 
// Driver Code
public static void Main()
{
    // Given Input
    int []arr = { 5, 6, 4, 9, 12 };
    int K = 2;
    int N = arr.Length;
 
    // Function Call
    Console.Write(ifPossible(arr, N, K));
}
}
 
// This code is contributed by SURENDRA_GANGWAR.

<script>
 
// JavaScript program for the above approach
 
 
// Function to check if it is possible
// to split the array into strictly
// increasing subsets of size atleast K
function ifPossible(arr, N, K)
{
 
    // Map to store frequency of elements
    let m = new Map();
 
    // Stores the frequency of the maximum
    // occurring element in the array
    let mx = 0;
 
    // Traverse the array
    for (let i = 0; i < N; i++) {
        m[arr[i]] += 1;
        if(m.has(arr[i])){
            m.set(arr[i], m.get([arr[i]]) + 1)
        }else{
            m.set(arr[i], 1)
        }
        mx = Math.max(mx, m.get(arr[i]));
    }
    // Stores the minimum count of elements
    // in a subset
    let sz = Math.floor(N / mx);
 
    // If sz is greater than k-1
    if (sz >= K) {
        return "Yes";
    }
    // Otherwise
    else {
 
        return "No";
    }
}
 
// Driver Code
 
    // Given Input
    let arr = [ 5, 6, 4, 9, 12 ];
    let K = 2;
    let N = arr.length;
 
    // Function Call
    document.write(ifPossible(arr, N, K));
     
</script>

Yes

Complejidad de tiempo: O(N*log(N)) 
Espacio auxiliar: O(N)