Dada una array arr[] de tamaño N y un entero positivo X , la tarea es dividir la array en el número máximo de subconjuntos tal que la multiplicación del elemento más pequeño de cada subconjunto con el recuento de elementos en los subconjuntos sea mayor que o igual a K. Imprima el recuento máximo posible de tales subconjuntos.
Ejemplos:
Entrada: arr[] = {1, 3, 3, 7}, X = 3
Salida: 3
Explicación: Divida la array en 3 subconjuntos { {1, 3}, {3}, {7} }. Por lo tanto, la salida requerida es 3.Entrada: arr[] = {2, 4, 2, 5, 1}, X = 2
Salida: 4
Planteamiento: El problema se puede resolver usando la técnica Greedy . Siga los pasos a continuación para resolver el problema:
- Ordene los elementos de la array en orden decreciente .
- Atraviese la array y realice un seguimiento del tamaño del subconjunto actual
- Como la array se ordena en orden decreciente, el elemento más a la derecha del subconjunto será el elemento más pequeño de la división actual.
- Entonces, si (tamaño del subconjunto actual * elemento actual) es mayor o igual a X , entonces incremente el conteo y restablezca el tamaño de la partición actual a 0 .
- Finalmente, imprima el conteo obtenido.
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 count maximum subsets into
// which the given array can be split such
// that it satisfies the given condition
void maxDivisions(int arr[], int N, int X)
{
// Sort the array in decreasing order
sort(arr, arr + N, greater<int>());
// Stores count of subsets possible
int maxSub = 0;
// Stores count of elements
// in current subset
int size = 0;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// Update size
size++;
// If product of the smallest element
// present in the current subset and
// size of current subset is >= K
if (arr[i] * size >= X) {
// Update maxSub
maxSub++;
// Update size
size = 0;
}
}
cout << maxSub << endl;
}
// Driver Code
int main()
{
// Given array
int arr[] = { 1, 3, 3, 7 };
// Size of the array
int N = sizeof(arr) / sizeof(arr[0]);
// Given value of X
int X = 3;
maxDivisions(arr, N, X);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to count maximum subsets into
// which the given array can be split such
// that it satisfies the given condition
static void maxDivisions(Integer arr[], int N, int X)
{
// Sort the array in decreasing order
Arrays.sort(arr,Collections.reverseOrder());
// Stores count of subsets possible
int maxSub = 0;
// Stores count of elements
// in current subset
int size = 0;
// Traverse the array arr[]
for (int i = 0; i < N; i++)
{
// Update size
size++;
// If product of the smallest element
// present in the current subset and
// size of current subset is >= K
if (arr[i] * size >= X)
{
// Update maxSub
maxSub++;
// Update size
size = 0;
}
}
System.out.print(maxSub +"\n");
}
// Driver Code
public static void main(String[] args)
{
// Given array
Integer arr[] = { 1, 3, 3, 7 };
// Size of the array
int N = arr.length;
// Given value of X
int X = 3;
maxDivisions(arr, N, X);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program for the above approach # Function to count maximum subsets into # which the given array can be split such # that it satisfies the given condition def maxDivisions(arr, N, X) : # Sort the array in decreasing order arr.sort(reverse = True) # Stores count of subsets possible maxSub = 0; # Stores count of elements # in current subset size = 0; # Traverse the array arr[] for i in range(N) : # Update size size += 1; # If product of the smallest element # present in the current subset and # size of current subset is >= K if (arr[i] * size >= X) : # Update maxSub maxSub += 1; # Update size size = 0; print(maxSub); # Driver Code if __name__ == "__main__" : # Given array arr = [ 1, 3, 3, 7 ]; # Size of the array N = len(arr); # Given value of X X = 3; maxDivisions(arr, N, X); # This code is contributed by AnkThon
C#
// C# program for the above approach
using System;
class GFG
{
// Function to count maximum subsets into
// which the given array can be split such
// that it satisfies the given condition
static void maxDivisions(int[] arr, int N, int X)
{
// Sort the array in decreasing order
Array.Sort(arr);
Array.Reverse(arr);
// Stores count of subsets possible
int maxSub = 0;
// Stores count of elements
// in current subset
int size = 0;
// Traverse the array arr[]
for (int i = 0; i < N; i++)
{
// Update size
size++;
// If product of the smallest element
// present in the current subset and
// size of current subset is >= K
if (arr[i] * size >= X)
{
// Update maxSub
maxSub++;
// Update size
size = 0;
}
}
Console.WriteLine(maxSub);
}
// Driver Code
public static void Main()
{
// Given array
int[] arr = { 1, 3, 3, 7 };
// Size of the array
int N = arr.Length;
// Given value of X
int X = 3;
maxDivisions(arr, N, X);
}
}
// This code is contributed by subhammahato348.
Javascript
<script>
// javascript program of the above approach
// Function to count maximum subsets into
// which the given array can be split such
// that it satisfies the given condition
function maxDivisions(arr, N, X)
{
// Sort the array in decreasing order
arr.sort();
// Stores count of subsets possible
let maxSub = 0;
// Stores count of elements
// in current subset
let size = 0;
// Traverse the array arr[]
for (let i = 0; i < N; i++)
{
// Update size
size++;
// If product of the smallest element
// present in the current subset and
// size of current subset is >= K
if (arr[i] * size >= X)
{
// Update maxSub
maxSub++;
// Update size
size = 0;
}
}
document.write(maxSub + "<br/>");
}
// Driver Code
// Given array
let arr = [ 1, 3, 3, 7 ];
// Size of the array
let N = arr.length;
// Given value of X
let X = 3;
maxDivisions(arr, N, X);
</script>
Producción:
3
Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ananyadixit8 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA