Dada una array, la tarea es el subconjunto divisible más grande en la array. Un subconjunto se llama divisible si para cada par (x, y) en el subconjunto, x divide a y o y divide a x.
Ejemplos:
Input : arr[] = {1, 16, 7, 8, 4}
Output : 16 8 4 1
In the output subset, for every pair,
either the first element divides second
or second divides first.
Input : arr[] = {2, 4, 3, 8}
Output : 8 4 2
Una solución simple es generar todos los subconjuntos de un conjunto dado . Para cada subconjunto generado, verifique si es divisible o no. Finalmente imprima el subconjunto divisible más grande.
Una solución eficiente implica seguir los pasos.
- Ordene todos los elementos de la array en orden creciente. El propósito de ordenar es asegurarse de que todos los divisores de un elemento aparezcan antes que él.
- Cree una array divCount[] del mismo tamaño que la array de entrada. divCount[i] almacena el tamaño del subconjunto divisible que termina en arr[i] (en una array ordenada). El valor mínimo de divCount[i] sería 1.
- Atraviesa todos los elementos de la array. Para cada elemento, encuentre un divisor arr[j] con el mayor valor de divCount[j] y almacene el valor de divCount[i] como divCount[j] + 1.
Implementación:
C++
// C++ program to find largest divisible
// subset in a given array
#include<bits/stdc++.h>
using namespace std;
// Prints largest divisible subset
void findLargest(int arr[], int n)
{
// We first sort the array so that all divisors
// of a number are before it.
sort(arr, arr+n);
// To store count of divisors of all elements
vector <int> divCount(n, 1);
// To store previous divisor in result
vector <int> prev(n, -1);
// To store index of largest element in maximum
// size subset
int max_ind = 0;
// In i'th iteration, we find length of chain
// ending with arr[i]
for (int i=1; i<n; i++)
{
// Consider every smaller element as previous
// element.
for (int j=0; j<i; j++)
{
if (arr[i]%arr[j] == 0)
{
if (divCount[i] < divCount[j] + 1)
{
divCount[i] = divCount[j]+1;
prev[i] = j;
}
}
}
// Update last index of largest subset if size
// of current subset is more.
if (divCount[max_ind] < divCount[i])
max_ind = i;
}
// Print result
int k = max_ind;
while (k >= 0)
{
cout << arr[k] << " ";
k = prev[k];
}
}
// Driven code
int main()
{
int arr[] = {1, 2, 17, 4};
int n = sizeof(arr)/sizeof(int);
findLargest(arr, n);
return 0;
}
Java
// Java program to find largest divisible
// subset in a given arrayimport java.io.*;
import java.util.*;
class DivSubset {
public static int[][] dp;
// Prints largest divisible subset
static void findLargest(int[] arr) {
// array that maintains the maximum index
// till which the condition is satisfied
int divCount[] = new int[arr.length];
// we will always have atleast one
// element divisible by itself
Arrays.fill(divCount, 1);
// maintain the index of the last increment
int prev[] = new int[arr.length];
Arrays.fill(prev, -1);
// index at which last increment happened
int max_ind = 0;
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
// only increment the maximum index if
// this iteration will increase it
if (arr[i] % arr[j] == 0 &&
divCount[i] < divCount[j] + 1) {
prev[i] = j;
divCount[i] = divCount[j] + 1;
}
}
// Update last index of largest subset if size
// of current subset is more.
if (divCount[i] > divCount[max_ind])
max_ind = i;
}
// Print result
int k = max_ind;
while (k >= 0) {
System.out.print(arr[k] + " ");
k = prev[k];
}
}
public static void main(String[] args) {
int[] x = { 1, 2, 17, 4};
// sort the array
Arrays.sort(x);
findLargest(x);
}
}
Python3
# Python 3 program to find largest divisible # subset in a given array # Prints largest divisible subset def findLargest(arr, n): # We first sort the array so that all divisors # of a number are before it. arr.sort(reverse = False) # To store count of divisors of all elements divCount = [1 for i in range(n)] # To store previous divisor in result prev = [-1 for i in range(n)] # To store index of largest element in maximum # size subset max_ind = 0 # In i'th iteration, we find length of chain # ending with arr[i] for i in range(1,n): # Consider every smaller element as previous # element. for j in range(i): if (arr[i] % arr[j] == 0): if (divCount[i] < divCount[j] + 1): divCount[i] = divCount[j]+1 prev[i] = j # Update last index of largest subset if size # of current subset is more. if (divCount[max_ind] < divCount[i]): max_ind = i # Print result k = max_ind while (k >= 0): print(arr[k],end = " ") k = prev[k] # Driven code if __name__ == '__main__': arr = [1, 2, 17, 4] n = len(arr) findLargest(arr, n) # This code is contributed by # Surendra_Gangwar
C#
// C# program to find largest divisible
// subset in a given array
using System;
public class DivSubset
{
public static int[,] dp;
// Prints largest divisible subset
static void findLargest(int[] arr)
{
// array that maintains the maximum index
// till which the condition is satisfied
int []divCount = new int[arr.Length];
// we will always have atleast one
// element divisible by itself
for(int i = 0; i < arr.Length; i++)
divCount[i] = 1;
// maintain the index of the last increment
int []prev = new int[arr.Length];
for(int i = 0; i < arr.Length; i++)
prev[i] = -1;
// index at which last increment happened
int max_ind = 0;
for (int i = 1; i < arr.Length; i++)
{
for (int j = 0; j < i; j++)
{
// only increment the maximum index if
// this iteration will increase it
if (arr[i] % arr[j] == 0 &&
divCount[i] < divCount[j] + 1)
{
prev[i] = j;
divCount[i] = divCount[j] + 1;
}
}
// Update last index of largest subset if size
// of current subset is more.
if (divCount[i] > divCount[max_ind])
max_ind = i;
}
// Print result
int k = max_ind;
while (k >= 0)
{
Console.Write(arr[k] + " ");
k = prev[k];
}
}
// Driver code
public static void Main(String[] args)
{
int[] x = { 1, 2, 17, 4};
// sort the array
Array.Sort(x);
findLargest(x);
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to find largest divisible
// subset in a given arrayimport java.io.*;
let dp;
// Prints largest divisible subset
function findLargest(arr)
{
// array that maintains the maximum index
// till which the condition is satisfied
let divCount = new Array(arr.length);
// we will always have atleast one
// element divisible by itself
for(let i=0;i<arr.length;i++)
{
divCount[i]=1;
}
// maintain the index of the last increment
let prev = new Array(arr.length);
for(let i=0;i<arr.length;i++)
{
prev[i]=-1;
}
// index at which last increment happened
let max_ind = 0;
for (let i = 1; i < arr.length; i++) {
for (let j = 0; j < i; j++) {
// only increment the maximum index if
// this iteration will increase it
if (arr[i] % arr[j] == 0 &&
divCount[i] < divCount[j] + 1) {
prev[i] = j;
divCount[i] = divCount[j] + 1;
}
}
// Update last index of largest subset if size
// of current subset is more.
if (divCount[i] > divCount[max_ind])
max_ind = i;
}
// Print result
let k = max_ind;
while (k >= 0) {
document.write(arr[k] + " ");
k = prev[k];
}
}
let x=[1, 2, 17, 4];
// sort the array
x.sort(function(a,b){return a-b;});
findLargest(x);
// This code is contributed by rag2127
</script>
Producción:
4 2 1
Complejidad de tiempo : O(n 2 )
Espacio auxiliar : O(n)
Este artículo es una contribución de DANISH_RAZA . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA