Dada una array , arr[] de longitud N y un entero K. El valor del i-ésimo elemento es arr[i] . La tarea es encontrar el número máximo de grupos tal que para cada grupo el producto del número de elementos en ese grupo y el elemento mínimo sea al menos K .
Nota: Cada elemento debe pertenecer exactamente a un grupo y algunos elementos pueden no ser parte de ningún grupo.
Ejemplos:
Entrada: N=5, arr[]={7, 2, 11, 9, 5}, K=10
Salida: 2
Explicación:
- Haz un grupo [11, 7] (tamaño del grupo=2) donde el producto del tamaño del grupo y el elemento mínimo del grupo es 2*7=14 que es mayor que k
- Haz otro grupo [9, 5] (tamaño del grupo=2) donde el producto del tamaño del grupo y el elemento mínimo del grupo es 2*5=10 es igual a k.
- Así podemos hacer máximo 2 grupos
Entrada: N=4, arr[]={1, 7, 3, 3}, K=11
Salida: 0
Explicación:
- Si hacemos un grupo [7, 3, 3] entonces el producto del tamaño del grupo (3) y el elemento mínimo del grupo (3) es 3*3=9 que es menor que k.
- Si hacemos un grupo [7, 3, 3, 1] entonces el producto del tamaño del grupo (4) y el elemento mínimo del grupo (1) es 1*4=4 que es menor que k.
- Si hacemos un grupo [7, 3], entonces el producto del tamaño del grupo (2) y el elemento mínimo del grupo (3) es 2*3=6, que es menor que k.
- Por lo tanto, no podemos hacer ningún grupo con la array dada tal que el producto del tamaño del grupo y el elemento mínimo sea al menos k.
Enfoque: El problema dado se puede resolver mediante un enfoque codicioso . Para maximizar la cantidad de grupos, ordene la array y comience a crear los grupos tomando primero los elementos más grandes porque esto nos ayudará a maximizar el elemento mínimo de cada grupo. Así se reducirá el número de elementos necesarios en cada grupo y maximizaremos el número de grupos. Siga los pasos a continuación para resolver el problema:
- Ordena la array dada en orden creciente .
- Inicialice las variables ans y count a 0 y 1 respectivamente, ans almacenará el número total de grupos que se pueden crear y count almacenará el tamaño del grupo actual.
- Recorra la array dada de [N-1 a 0] usando la variable i y realice estos pasos:
- Si el producto de arr[i] (elemento mínimo del grupo actual) y cuenta (tamaño del grupo actual) es mayor que k , entonces aumente la cuenta (número total de grupos) en 1 e inicialice la cuenta en 1.
- De lo contrario, aumente el número de elementos en el grupo actual en 1 .
- Después de completar estos pasos, imprima el valor de ans como respuesta.
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 return the maximum number
// of groups that can be formed from given array
int maximumgroups(vector<int>& arr, int N, int k)
{
// Sorting the given array in increasing order
sort(arr.begin(), arr.end());
int ans = 0, count = 1;
// Start creating the groups by taking
// the bigger elements first because this
// will help us in maximizing our
// minimum element of each group
for (int i = N - 1; i >= 0; i--) {
// If the product of minimum element of
// current group and count is greater equal
// to k then increase the ans by one and
// initialize the count to 1
if (arr[i] * count >= k) {
ans++;
count = 1;
}
// Otherwise increase the number of elements
// in the current group by one
else {
count++;
}
}
// Return the maximum number of groups possible
return ans;
}
// Driver Code
int main()
{
int N = 5;
int k = 10;
vector<int> arr = { 7, 11, 2, 9, 5 };
int res = maximumgroups(arr, N, k);
cout << res << endl;
return 0;
}
Java
// Java program for the above approach
import java.util.Arrays;
class GFG {
// Function to return the maximum number
// of groups that can be formed from given array
public static int maximumgroups(int[] arr, int N, int k) {
// Sorting the given array in increasing order
Arrays.sort(arr);
int ans = 0, count = 1;
// Start creating the groups by taking
// the bigger elements first because this
// will help us in maximizing our
// minimum element of each group
for (int i = N - 1; i >= 0; i--) {
// If the product of minimum element of
// current group and count is greater equal
// to k then increase the ans by one and
// initialize the count to 1
if (arr[i] * count >= k) {
ans++;
count = 1;
}
// Otherwise increase the number of elements
// in the current group by one
else {
count++;
}
}
// Return the maximum number of groups possible
return ans;
}
// Driver Code
public static void main(String args[]) {
int N = 5;
int k = 10;
int[] arr = { 7, 11, 2, 9, 5 };
int res = maximumgroups(arr, N, k);
System.out.println(res);
}
}
// This code is contributed by saurabh_jaiswal.
Python3
# Python 3 program for the above approach # Function to return the maximum number # of groups that can be formed from given array def maximumgroups(arr, N, k): # Sorting the given array in increasing order arr.sort(); ans = 0 count = 1; # Start creating the groups by taking # the bigger elements first because this # will help us in maximizing our # minimum element of each group for i in range(N - 1, -1, -1): # If the product of minimum element of # current group and count is greater equal # to k then increase the ans by one and # initialize the count to 1 if (arr[i] * count >= k): ans += 1 count = 1; # Otherwise increase the number of elements # in the current group by one else: count += 1 # Return the maximum number of groups possible return ans; # Driver Code if __name__ == "__main__": N = 5; k = 10; arr = [ 7, 11, 2, 9, 5 ]; res = maximumgroups(arr, N, k); print(res ); # This code is contributed by ukasp.
C#
// C# program for the above approach
using System;
public class GFG {
// Function to return the maximum number
// of groups that can be formed from given array
public static int maximumgroups(int[] arr, int N, int k) {
// Sorting the given array in increasing order
Array.Sort(arr);
int ans = 0, count = 1;
// Start creating the groups by taking
// the bigger elements first because this
// will help us in maximizing our
// minimum element of each group
for (int i = N - 1; i >= 0; i--) {
// If the product of minimum element of
// current group and count is greater equal
// to k then increase the ans by one and
// initialize the count to 1
if (arr[i] * count >= k) {
ans++;
count = 1;
}
// Otherwise increase the number of elements
// in the current group by one
else {
count++;
}
}
// Return the maximum number of groups possible
return ans;
}
// Driver Code
public static void Main(String []args) {
int N = 5;
int k = 10;
int[] arr = { 7, 11, 2, 9, 5 };
int res = maximumgroups(arr, N, k);
Console.WriteLine(res);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript code for the above approach
// Function to return the maximum number
// of groups that can be formed from given array
function maximumgroups(arr, N, k) {
// Sorting the given array in increasing order
arr.sort(function (a, b) { return a - b })
let ans = 0, count = 1;
// Start creating the groups by taking
// the bigger elements first because this
// will help us in maximizing our
// minimum element of each group
for (let i = N - 1; i >= 0; i--) {
// If the product of minimum element of
// current group and count is greater equal
// to k then increase the ans by one and
// initialize the count to 1
if (arr[i] * count >= k) {
ans++;
count = 1;
}
// Otherwise increase the number of elements
// in the current group by one
else {
count++;
}
}
// Return the maximum number of groups possible
return ans;
}
// Driver Code
let N = 5;
let k = 10;
let arr = [7, 11, 2, 9, 5];
let res = maximumgroups(arr, N, k);
document.write(res)
// This code is contributed by Potta Lokesh
</script>
Producción
2
Complejidad de tiempo: O(N*(log(N)))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por vanshikapoor y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA