Número máximo de subconjuntos en los que se puede dividir una array de modo que el producto de sus mínimos con el tamaño de los subconjuntos sea al menos K

Dada una array arr[] que consta de N enteros y un entero K , la tarea es encontrar el número máximo de subconjuntos disjuntos en los que se puede dividir la array dada de tal manera que el producto del elemento mínimo de cada subconjunto con el tamaño de la el subconjunto es al menos K .

Ejemplos:

Entrada: arr[] = {7, 11, 2, 9, 5}, K = 10
Salida: 2
Explicación:
Todos estos subconjuntos disjuntos posibles son:
Subconjunto {11}: Producto del mínimo y el tamaño del subconjunto = 11 * 1 = 11 ( > 10).
Subconjunto {5, 9, 7}: Producto de mínimo y tamaño del subconjunto = 5 * 3 = 15( > 10).
Por lo tanto, el número total de subconjuntos formados es 2.

Entrada: arr[] = {1, 3, 3, 7}, K = 12
Salida: 0

Enfoque: El problema dado se puede resolver con avidez en base a las siguientes observaciones:

  • Como se indica en el enunciado del problema, el producto del elemento mínimo del subconjunto formado y la longitud del subconjunto debe ser al menos K , por lo que para maximizar el número de subconjuntos, el elemento máximo de la array se puede agrupar al elemento mínimo de el subconjunto
  • Entonces, la idea es maximizar el elemento mínimo del subconjunto uno por uno, lo que maximiza el recuento del subconjunto.

Siga los pasos a continuación para resolver el problema:

  • Inicialice una variable, digamos contar como 0 , para almacenar el número máximo de subconjuntos formados.
  • Inicialice una variable, digamos length como 0 , para almacenar la longitud del subconjunto.
  • Ordene la array en orden descendente .
  • Recorra la array dada arr[] y realice los siguientes pasos:
    • Incremente el valor de longitud en 1 .
    • Si el valor de (arr[i] * length) es mayor que K , incremente el valor de la cuenta en 1 y actualice el valor de length como 0 .
  • Después de completar los pasos anteriores, imprima el valor de count como el número máximo resultante de subconjuntos formados.

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum number
// of subsets possible such that
// product of their minimums and the
// size of subsets are at least K
int maximumSubset(int arr[], int N,
                  int K)
{
    // Sort the array in
    // descending order
    sort(arr, arr + N, greater<int>());
 
    // Stores the size of
    // the current subset
    int len = 0;
 
    // Stores the count of subsets
    int ans = 0;
 
    // Traverse the array arr[]
    for (int i = 0; i < N; i++) {
 
        // Increment length of the
        // subsets by 1
        len++;
 
        // If arr[i] * len >= K
        if (arr[i] * len >= K) {
 
            // Increment ans by one
            ans++;
 
            // Update len
            len = 0;
        }
    }
 
    // Return the maximum possible
    // subsets formed
    return ans;
}
 
// Driver Code
int main()
{
    int arr[] = { 7, 11, 2, 9, 5 };
    int K = 10;
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << maximumSubset(arr, N, K);
 
    return 0;
}

Java

import java.util.*;
public class GFG
{
 
  // Function to reverse the sorted array
  public static void reverse(int[] arr)
  {
 
    // Length of the array
    int n = arr.length;
 
    // Swaping the first half elements with last half
    // elements
    for (int i = 0; i < n / 2; i++) {
 
      // Storing the first half elements temporarily
      int temp = arr[i];
 
      // Assigning the first half to the last half
      arr[i] = arr[n - i - 1];
 
      // Assigning the last half to the first half
      arr[n - i - 1] = temp;
    }
  }
 
  // Function to find the maximum number
  // of subsets possible such that
  // product of their minimums and the
  // size of subsets are at least K
  public static int maximumSubset(int arr[], int N, int K)
  {
     
    // Sort the array in
    // descending order
    Arrays.sort(arr);
    reverse(arr);
    // Stores the size of
    // the current subset
    int len = 0;
 
    // Stores the count of subsets
    int ans = 0;
 
    // Traverse the array arr[]
    for (int i = 0; i < N; i++) {
 
      // Increment length of the
      // subsets by 1
      len++;
 
      // If arr[i] * len >= K
      if (arr[i] * len >= K) {
 
        // Increment ans by one
        ans++;
 
        // Update len
        len = 0;
      }
    }
 
    // Return the maximum possible
    // subsets formed
    return ans;
  }
 
  // Driver Code
  public static void main(String args[]) {
    int arr[] = { 7, 11, 2, 9, 5 };
    int K = 10;
    int N =arr.length;
    System.out.println(maximumSubset(arr, N, K));
  }
}
 
// This code is contributed by SoumikMondal

Python3

# Python 3 program for the above approach
 
# Function to find the maximum number
# of subsets possible such that
# product of their minimums and the
# size of subsets are at least K
def maximumSubset(arr, N,
                  K):
 
    # Sort the array in
    # descending order
    arr.sort(reverse = True)
 
    # Stores the size of
    # the current subset
    len = 0
 
    # Stores the count of subsets
    ans = 0
 
    # Traverse the array arr[]
    for i in range(N):
 
        # Increment length of the
        # subsets by 1
        len += 1
 
        # If arr[i] * len >= K
        if (arr[i] * len >= K):
 
            # Increment ans by one
            ans += 1
 
            # Update len
            len = 0
 
    # Return the maximum possible
    # subsets formed
    return ans
 
# Driver Code
if __name__ == "__main__":
 
    arr = [7, 11, 2, 9, 5]
    K = 10
    N = len(arr)
    print(maximumSubset(arr, N, K))
 
    # This code is contributed by ukasp.

C#

using System;
 
public class GFG
{
 
    // Function to reverse the sorted array
    public static void reverse(int[] arr)
    {
 
        // Length of the array
        int n = arr.Length;
 
        // Swaping the first half elements with last half
        // elements
        for (int i = 0; i < n / 2; i++) {
 
            // Storing the first half elements temporarily
            int temp = arr[i];
 
            // Assigning the first half to the last half
            arr[i] = arr[n - i - 1];
 
            // Assigning the last half to the first half
            arr[n - i - 1] = temp;
        }
    }
 
    // Function to find the maximum number
    // of subsets possible such that
    // product of their minimums and the
    // size of subsets are at least K
    public static int maximumSubset(int []arr, int N, int K)
    {
 
        // Sort the array in
        // descending order
        Array.Sort(arr);
        reverse(arr);
       
        // Stores the size of
        // the current subset
        int len = 0;
 
        // Stores the count of subsets
        int ans = 0;
 
        // Traverse the array []arr
        for (int i = 0; i < N; i++)
        {
 
            // Increment length of the
            // subsets by 1
            len++;
 
            // If arr[i] * len >= K
            if (arr[i] * len >= K)
            {
 
                // Increment ans by one
                ans++;
 
                // Update len
                len = 0;
            }
        }
 
        // Return the maximum possible
        // subsets formed
        return ans;
    }
 
    // Driver Code
    public static void Main(String []args)
    {
        int []arr = { 7, 11, 2, 9, 5 };
        int K = 10;
        int N = arr.Length;
        Console.WriteLine(maximumSubset(arr, N, K));
    }
}
 
// This code is contributed by aashish1995.

Javascript

<script>
 
// JavaScript program to implement
// the above approach
 
  // Function to reverse the sorted array
  function reverse(arr)
  {
  
    // Length of the array
    let n = arr.length;
  
    // Swaping the first half elements with last half
    // elements
    for (let i = 0; i < n / 2; i++) {
  
      // Storing the first half elements temporarily
      let temp = arr[i];
  
      // Assigning the first half to the last half
      arr[i] = arr[n - i - 1];
  
      // Assigning the last half to the first half
      arr[n - i - 1] = temp;
    }
  }
  
  // Function to find the maximum number
  // of subsets possible such that
  // product of their minimums and the
  // size of subsets are at least K
  function maximumSubset(arr, N, K)
  {
      
    // Sort the array in
    // descending order
    arr.sort();
    arr.reverse();
    // Stores the size of
    // the current subset
    let len = 0;
  
    // Stores the count of subsets
    let ans = 0;
  
    // Traverse the array arr[]
    for (let i = 0; i < N; i++) {
  
      // Increment length of the
      // subsets by 1
      len++;
  
      // If arr[i] * len >= K
      if (arr[i] * len >= K) {
  
        // Increment ans by one
        ans++;
  
        // Update len
        len = 0;
      }
    }
  
    // Return the maximum possible
    // subsets formed
    return ans;
  }
 
// Driver code
 
    let arr = [ 7, 11, 2, 9, 5 ];
    let K = 10;
    let N =arr.length;
    document.write(maximumSubset(arr, N, K));
            
</script>
Producción: 

2

 

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

Publicación traducida automáticamente

Artículo escrito por arnav21 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *