Dada una array arr[] que consta de N enteros y un entero positivo K , la tarea es maximizar el número de subconjuntos que tienen un producto de su tamaño y su elemento máximo al menos K dividiendo el elemento de la array en subconjuntos disjuntos.
Ejemplos:
Entrada: N = 5, K = 4, arr[] = {1, 5, 4, 2, 3}
Salida: 3
Explicación:
La array se puede dividir en 3 subconjuntos posibles {1, 2}, {4, 3} y {5}, cuyo producto del elemento máximo de los subconjuntos con su tamaño es al menos K(= 4). Por lo tanto, la cuenta de dichos subconjuntos es 3.Entrada: N = 4, K = 81, arr[] = {12, 8, 14, 20}
Salida: 0
Enfoque: El problema dado se puede resolver observando el hecho de que los elementos que son al menos K pueden formar un grupo adecuado por sí solos. Para extraer el número máximo de grupos que no tienen elementos mayores que iguales a K , la idea es comenzar incluyendo elementos desde el elemento mínimo de la array arr[] y luego seguir avanzando hacia elementos más grandes hasta que se encuentre un grupo adecuado . formado. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos count como 0 , que almacene el conteo resultante de subconjuntos y pre como 1 para almacenar el tamaño inicial del grupo.
- Ordene la array dada arr[] en orden ascendente .
- Itere sobre el rango [0, N] usando una variable, digamos i , y realice los siguientes pasos:
- Si el valor de arr[i] * pre es al menos K , incremente el valor de count en 1 y establezca el valor de pre en 1 .
- De lo contrario, incremente el valor de pre en 1 .
- Después de realizar los pasos anteriores, imprima el valor de conteo como el conteo resultante de subconjuntos.
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 into which
// the array can be split
void countOfSubsets(int arr[], int N,
int K)
{
// Stores the maximum number of
// subsets
int count = 0;
int pre = 1;
// Sort the given array
sort(arr, arr + N);
// Iterate over the range [0, N]
for (int i = 0; i < N; i++) {
// If current subset satisfies
// the given condition
if (arr[i] * pre >= K) {
count++;
pre = 1;
}
// Otherwise, increment pre
else {
pre++;
}
}
cout << count;
}
// Driver Code
int main()
{
int arr[] = { 1, 5, 4, 2, 3 };
int K = 2;
int N = sizeof(arr) / sizeof(arr[0]);
countOfSubsets(arr, N, K);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.util.*;
class GFG {
// Function to find the maximum
// number of subsets into which
// the array can be split
public static void countOfSubsets(int[] arr, int N,
int K)
{
// Stores the maximum number of
// subsets
int count = 0;
int pre = 1;
// Sort the given array
Arrays.sort(arr);
// Iterate over the range [0, N]
for (int i = 0; i < N; i++) {
// If current subset satisfies
// the given condition
if (arr[i] * pre >= K) {
count++;
pre = 1;
}
// Otherwise, increment pre
else {
pre++;
}
}
System.out.println(count);
}
public static void main(String[] args)
{
int[] arr = { 1, 5, 4, 2, 3 };
int K = 2;
int N = 5;
countOfSubsets(arr, N, K);
}
}
Python3
# Function to find the maximum # number of subsets into which # the array can be split def countOfSubsets(arr, N, K): # Stores the maximum number of # subsets count = 0 pre = 1 # Sort the given array arr.sort() # Iterate over the range [0, N] for i in range(N): # If current subset satisfies # the given condition if arr[i] * pre >= K: count = count + 1 pre = 1 # Otherwise, increment pre else: pre = pre + 1 print(count) # Driver code arr = [1, 5, 4, 2, 3] N = 5 K = 2 countOfSubsets(arr, N, K) # This code is contributed by maddler.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the maximum
// number of subsets into which
// the array can be split
static void countOfSubsets(int []arr, int N,
int K)
{
// Stores the maximum number of
// subsets
int count = 0;
int pre = 1;
// Sort the given array
Array.Sort(arr);
// Iterate over the range [0, N]
for (int i = 0; i < N; i++) {
// If current subset satisfies
// the given condition
if (arr[i] * pre >= K) {
count++;
pre = 1;
}
// Otherwise, increment pre
else {
pre++;
}
}
Console.Write(count);
}
// Driver Code
public static void Main()
{
int []arr = { 1, 5, 4, 2, 3 };
int K = 2;
int N = arr.Length;
countOfSubsets(arr, N, K);
}
}
// This code is contributed by ipg2016107.
Javascript
<script>
// JavaScript program for the above approach;
// Function to find the maximum
// number of subsets into which
// the array can be split
function countOfSubsets(arr, N,
K) {
// Stores the maximum number of
// subsets
let count = 0;
let pre = 1;
// Sort the given array
arr.sort(function (a, b) { return a - b });
// Iterate over the range [0, N]
for (let i = 0; i < N; i++) {
// If current subset satisfies
// the given condition
if (arr[i] * pre >= K) {
count++;
pre = 1;
}
// Otherwise, increment pre
else {
pre++;
}
}
document.write(count);
}
// Driver Code
let arr = [1, 5, 4, 2, 3];
let K = 2;
let N = arr.length;
countOfSubsets(arr, N, K);
// This code is contributed by Potta Lokesh
</script>
4
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por parthmanchanda81 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA