Dado un entero N y una array arr[] que tiene M enteros, la tarea es encontrar el tamaño máximo del subconjunto tal que el producto de todos los elementos del subconjunto sea un factor de N .
Ejemplos:
Entrada: N = 12, arr[] = {2, 3, 4}
Salida: 2
Explicación: La array dada 5 subconjuntos tales que el producto de todos los elementos del subconjunto es un factor de 12. Son {2}, { 3}, {4}, {2, 3} como (2 * 3) = 6 y {3, 4} como (3 * 4) = 12. Por lo tanto, el tamaño máximo del subconjunto válido es 2.Entrada: N = 64, arr[] = {1, 2, 4, 8, 16, 32}
Salida: 4
Enfoque: el problema dado se puede resolver usando la recursividad recorriendo todos los subconjuntos de la array dada arr[] y haciendo un seguimiento del tamaño de los subconjuntos de manera que N % (producto de los elementos del subconjunto) = 0 . Además, para que el producto de los elementos del subconjunto sea un factor de N , todos los elementos individuales de la array arr [] también deben ser un factor de N. Por lo tanto, el problema anterior se puede resolver siguiendo los siguientes pasos:
- Cree una función recursiva maximizarSubset() , que calcula el tamaño máximo del subconjunto requerido.
- Si se han recorrido todos los elementos de la array dada arr[] , devuelve 0, que es el caso base.
- Itere sobre todos los elementos de la array arr[] y si N % arr[i] = 0 , incluya arr[i] en un subconjunto y llame recursivamente a N = N/arr[i] para los elementos restantes de la array.
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 size of
// the subset such that the product of
// subset elements is a factor of N
int maximizeSubset(int N, int arr[],
int M, int x = 0)
{
// Base Case
if (x == M) {
return 0;
}
// Stores maximum size of valid subset
int ans = 0;
// Traverse the given array
for (int i = x; i < M; i++) {
// If N % arr[i] = 0, include arr[i]
// in a subset and recursively call
// for the remaining array integers
if (N % arr[i] == 0) {
ans = max(
ans, maximizeSubset(
N / arr[i], arr,
M, x + 1)
+ 1);
}
}
// Return Answer
return ans;
}
// Driver Code
int main()
{
int N = 64;
int arr[] = { 1, 2, 4, 8, 16, 32 };
int M = sizeof(arr) / sizeof(arr[0]);
cout << maximizeSubset(N, arr, M);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find the maximum size of
// the subset such that the product of
// subset elements is a factor of N
static int maximizeSubset(int N, int[] arr, int M,
int x)
{
// Base Case
if (x == M) {
return 0;
}
// Stores maximum size of valid subset
int ans = 0;
// Traverse the given array
for (int i = x; i < M; i++) {
// If N % arr[i] = 0, include arr[i]
// in a subset and recursively call
// for the remaining array integers
if (N % arr[i] == 0) {
ans = Math.max(ans,
maximizeSubset(N / arr[i],
arr, M, x + 1)
+ 1);
}
}
// Return Answer
return ans;
}
// Driver Code
public static void main(String[] args)
{
int N = 64;
int[] arr = { 1, 2, 4, 8, 16, 32 };
int M = arr.length;
System.out.println(maximizeSubset(N, arr, M, 0));
}
}
// This code is contributed by ukasp.
Python3
# Python Program to implement # the above approach # Function to find the maximum size of # the subset such that the product of # subset elements is a factor of N def maximizeSubset(N, arr, M, x=0): # Base Case if (x == M): return 0 # Stores maximum size of valid subset ans = 0 # Traverse the given array for i in range(x, M): # If N % arr[i] = 0, include arr[i] # in a subset and recursively call # for the remaining array integers if (N % arr[i] == 0): ans = max( ans, maximizeSubset( N // arr[i], arr, M, x + 1) + 1) # Return Answer return ans # Driver Code N = 64 arr = [1, 2, 4, 8, 16, 32] M = len(arr) print(maximizeSubset(N, arr, M)) # This code is contributed by Saurabh jaiswal
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the maximum size of
// the subset such that the product of
// subset elements is a factor of N
static int maximizeSubset(int N, int []arr,
int M, int x)
{
// Base Case
if (x == M) {
return 0;
}
// Stores maximum size of valid subset
int ans = 0;
// Traverse the given array
for (int i = x; i < M; i++) {
// If N % arr[i] = 0, include arr[i]
// in a subset and recursively call
// for the remaining array integers
if (N % arr[i] == 0) {
ans = Math.Max(
ans, maximizeSubset(
N / arr[i], arr,
M, x + 1)
+ 1);
}
}
// Return Answer
return ans;
}
// Driver Code
public static void Main()
{
int N = 64;
int []arr = { 1, 2, 4, 8, 16, 32 };
int M = arr.Length;
Console.Write(maximizeSubset(N, arr, M,0));
}
}
// This code is contributed by ipg2016107.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find the maximum size of
// the subset such that the product of
// subset elements is a factor of N
function maximizeSubset(N, arr,
M, x = 0)
{
// Base Case
if (x == M) {
return 0;
}
// Stores maximum size of valid subset
let ans = 0;
// Traverse the given array
for (let i = x; i < M; i++) {
// If N % arr[i] = 0, include arr[i]
// in a subset and recursively call
// for the remaining array integers
if (N % arr[i] == 0) {
ans = Math.max(
ans, maximizeSubset(
Math.floor(N / arr[i]), arr,
M, x + 1)
+ 1);
}
}
// Return Answer
return ans;
}
// Driver Code
let N = 64;
let arr = [1, 2, 4, 8, 16, 32];
let M = arr.length;
document.write(maximizeSubset(N, arr, M));
// This code is contributed by Potta Lokesh
</script>
4
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ramandeep8421 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA