Dada una array arr[] de tamaño N , la tarea es dividir la array en el número mínimo de subconjuntos de manera que cada elemento pertenezca exactamente a un subconjunto y sea divisible por el elemento mínimo presente en cada subconjunto.
Ejemplos:
Entrada: arr[] = {10, 2, 3, 5, 4, 2}
Salida: 3
Explicación:
Los tres grupos posibles son:
- {5, 10}, donde todo el elemento es divisible por 5 (elemento mínimo).
- {2, 2, 4}, donde todo el elemento es divisible por 2 (elemento mínimo).
- {3}, donde todo el elemento es divisible por 3 (elemento mínimo).
Entrada: arr[] = {50, 50, 50, 50, 50}
Salida: 1
Enfoque: el problema se puede resolver utilizando Clasificación y encontrando el mínimo para cada subconjunto. Siga los pasos a continuación para resolver el problema:
- Ordene la array arr[] en orden ascendente .
- Inicialice una variable, digamos ans , con 0 y una array vis[] , para almacenar los elementos de la array visitados.
- Marque todas las posiciones de la array vis[] con 0 que representa las posiciones que no han sido visitadas.
- Recorra la array dada arr[] y realice los siguientes pasos:
- Si no se visita el elemento arr[i] , entonces:
- Considérelo como un mínimo para el nuevo subconjunto e incremente ans en 1 .
- Itere sobre el rango [i + 1, N – 1] usando la variable j y si el elemento arr[j] no se visita y es divisible por arr[i] , entonces establezca vis[j] = 1 .
- Repita los pasos anteriores para cada índice.
- Si no se visita el elemento arr[i] , entonces:
- Después de completar los pasos anteriores, imprima el valor de ans como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#define LL long long
#define MM 1000000007
using namespace std;
// Function to find the minimum number
// of subsets into which given array
// can be split such that the given
// conditions are satisfied
void groupDivision(int arr[], int n)
{
LL z, i, j, ans;
// Sort the given array arr[]
sort(arr, arr + n);
// Initialize answer
ans = 0;
LL vis[n + 5] = { 0 };
// Iterate for the smaller value
// which has not been visited
for (i = 0; i < n; i++) {
if (!vis[i]) {
// Mark all elements that
// are divisible by arr[i]
for (j = i + 1; j < n; j++) {
// If jth index has already
// been visited
if (vis[j] == 1)
continue;
if (arr[j] % arr[i] == 0)
// Mark the jth index
// as visited
vis[j] = 1;
}
// Increment ans by 1
ans++;
}
}
// Print the value of ans
cout << ans;
}
// Driver Code
int main()
{
int arr[] = { 10, 2, 3, 5, 4, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
groupDivision(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
static int MM = 1000000007;
// Function to find the minimum number
// of subsets into which given array
// can be split such that the given
// conditions are satisfied
static void groupDivision(int arr[], int n)
{
int z, i, j, ans;
// Sort the given array arr[]
Arrays.sort(arr);
// Initialize answer
ans = 0;
int[] vis = new int[n + 5];
Arrays.fill(vis, 0);
// Iterate for the smaller value
// which has not been visited
for (i = 0; i < n; i++) {
if (vis[i] == 0) {
// Mark all elements that
// are divisible by arr[i]
for (j = i + 1; j < n; j++) {
// If jth index has already
// been visited
if (vis[j] == 1)
continue;
if (arr[j] % arr[i] == 0)
// Mark the jth index
// as visited
vis[j] = 1;
}
// Increment ans by 1
ans++;
}
}
// Print the value of ans
System.out.println(ans);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 10, 2, 3, 5, 4, 2 };
int N = arr.length;
groupDivision(arr, N);
}
}
// This code is contributed by code_hunt.
Python3
# Python3 program for the above approach MM = 1000000007 # Function to find the minimum number # of subsets into which given array # can be split such that the given # conditions are satisfied def groupDivision(arr, n): global MM ans = 0 # Sort the given array arr[] arr = sorted(arr) vis = [0]*(n + 5) # Iterate for the smaller value # which has not been visited for i in range(n): if (not vis[i]): # Mark all elements that # are divisible by arr[i] for j in range(i + 1, n): # If jth index has already # been visited if (vis[j] == 1): continue if (arr[j] % arr[i] == 0): # Mark the jth index # as visited vis[j] = 1 # Increment ans by 1 ans += 1 # Print the value of ans print (ans) # Driver Code if __name__ == '__main__': arr =[10, 2, 3, 5, 4, 2] N = len(arr) groupDivision(arr, N) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
class GFG
{
static int MM = 1000000007;
// Function to find the minimum number
// of subsets into which given array
// can be split such that the given
// conditions are satisfied
static void groupDivision(int[] arr, int n)
{
int z, i, j, ans;
// Sort the given array arr[]
Array.Sort(arr);
// Initialize answer
ans = 0;
int[] vis = new int[n + 5];
for (i = 0; i < n; i++) {
vis[i] = 0;
}
// Iterate for the smaller value
// which has not been visited
for (i = 0; i < n; i++) {
if (vis[i] == 0) {
// Mark all elements that
// are divisible by arr[i]
for (j = i + 1; j < n; j++) {
// If jth index has already
// been visited
if (vis[j] == 1)
continue;
if (arr[j] % arr[i] == 0)
// Mark the jth index
// as visited
vis[j] = 1;
}
// Increment ans by 1
ans++;
}
}
// Print the value of ans
Console.Write(ans);
}
// Driver Code
static public void Main ()
{
int[] arr = { 10, 2, 3, 5, 4, 2 };
int N = arr.Length;
groupDivision(arr, N);
}
}
// This code is contributed by code_hunt.
Javascript
<script>
// Javascript program for the above approach
var MM = 1000000007;
// Creating the bblSort function
function bblSort(arr)
{
for(var i = 0; i < arr.length; i++)
{
// Last i elements are already in place
for(var j = 0;
j < (arr.length - i - 1);
j++)
{
// Checking if the item at present iteration
// is greater than the next iteration
if (arr[j] > arr[j + 1])
{
// If the condition is true
// then swap them
var temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
}
// Return the sorted array
return (arr);
}
// Function to find the minimum number
// of subsets into which given array
// can be split such that the given
// conditions are satisfied
function groupDivision(arr, n)
{
var z, i, j, ans;
// Sort the given array arr
arr = bblSort(arr);
// Initialize answer
ans = 0;
var vis = Array(n + 5).fill(0);
// Iterate for the smaller value
// which has not been visited
for(i = 0; i < n; i++)
{
if (vis[i] == 0)
{
// Mark all elements that
// are divisible by arr[i]
for(j = i + 1; j < n; j++)
{
// If jth index has already
// been visited
if (vis[j] == 1)
continue;
if (arr[j] % arr[i] == 0)
// Mark the jth index
// as visited
vis[j] = 1;
}
// Increment ans by 1
ans++;
}
}
// Print the value of ans
document.write(ans);
}
// Driver Code
var arr = [ 10, 2, 3, 5, 4, 2 ];
var N = arr.length;
groupDivision(arr, N);
// This code is contributed by gauravrajput1
</script>
Producción:
3
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ujjwalgoel1103 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA