Dada una array arr[] de tamaño N , la tarea es encontrar el número de subconjuntos no vacíos presentes en la array de modo que cada elemento ( excepto el último ) en el subconjunto sea un factor del siguiente elemento adyacente presente en ese subconjunto . Los elementos de un subconjunto se pueden reorganizar , por lo tanto, si cualquier reordenamiento de un subconjunto satisface la condición, ese subconjunto se contará. Sin embargo, este subconjunto se debe contar solo una vez.
Ejemplos:
Entrada: arr[] = {2, 3, 6, 8}
Salida: 7
Explicación:
Los subconjuntos requeridos son: {2}, {3}, {6}, {8}, {2, 6}, {8, 2}, {3, 6}.
Dado que los subconjuntos {2}, {3}, {6}, {8} contienen un solo número, se incluyen en la respuesta.
En el subconjunto {2, 6}, 2 es un factor de 6.
En el subconjunto {3, 6}, 3 es un factor de 6.
{8, 2} cuando se reorganiza en {2, 8}, satisface la condición requerida .Entrada: arr[] = {16, 18, 6, 7, 2, 19, 20, 9}
Salida: 15
Enfoque ingenuo: la idea más simple es generar todos los subconjuntos posibles de la array e imprimir el recuento de esos subconjuntos cuyo elemento adyacente (arr[i], arr[i + 1]) , arr[i] es un factor de arr[i + 1] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
// Function to calculate each subset
// for the array using bit masking
set<int> getSubset(int n, int* arr,
int mask)
{
// Stores the unique elements
// of the array arr[]
set<int> subset;
// Traverse the array
for (int i = 0; i < n; i++) {
// Get the ith bit of the mask
int b = (mask & (1 << i));
// ith bit of mask is set then
// include the corresponding
// element in subset
if (b != 0) {
subset.insert(arr[i]);
}
}
return subset;
}
// Function to count the subsets
// that satisfy the given condition
int countSets(int n, set<int>* power_set)
{
// Store the count of subsets
int count = 0;
// Iterate through all the sets
// in the power set
for (int i = 1; i < (1 << n); i++) {
// Initially, set flag as true
bool flag = true;
int N = power_set[i].size();
// Convert the current subset
// into an array
int* temp = new int[N];
auto it = power_set[i].begin();
for (int j = 0;
it != power_set[i].end();
j++, it++) {
temp[j] = *it;
}
// Check for any index, i,
// a[i] is a factor of a[i+1]
for (int k1 = 1, k0 = 0; k1 < N;) {
if (temp[k1] % temp[k0] != 0) {
flag = false;
break;
}
if (k0 > 0)
k0--;
else {
k1++;
k0 = k1 - 1;
}
}
// If flag is still set, then
// update the count
if (flag)
count = 1LL * (count + 1) % mod;
delete[] temp;
}
// Return the final count
return count;
}
// Function to generate power set of
// the given array arr[]
void generatePowerSet(int arr[], int n)
{
// Declare power set of size 2^n
set<int>* power_set
= new set<int>[1 << n];
// Represent each subset using
// some mask
int mask = 0;
for (int i = 0; i < (1 << n); i++) {
power_set[i] = getSubset(n, arr, mask);
mask++;
}
// Find the required number of
// subsets
cout << countSets(n, power_set) % mod;
delete[] power_set;
}
// Driver Code
int main()
{
int arr[] = { 16, 18, 6, 7, 2, 19, 20, 9 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
generatePowerSet(arr, N);
return 0;
}
Producción:
15
Complejidad temporal: O(N*2 N )
Espacio auxiliar: O(1)
Enfoque basado en HashMap : para optimizar el enfoque anterior, la idea es utilizar un hashmap y una array dp[] para almacenar los elementos de la array de manera ordenada y también llevar un recuento de los subconjuntos. Para el índice i, dp[arr[i]] almacenará el número de todos los subconjuntos que satisfacen las condiciones dadas que terminan en el índice i . Siga los pasos a continuación para resolver el problema:
- Inicialice cnt como 0 para almacenar el número de subconjuntos requeridos.
- Inicialice un hashmap, dp y marque dp[arr[i]] con 1 por cada i sobre el rango [0, N – 1] .
- Recorra el arreglo dp[] usando la variable i y un recorrido anidado desde i para comenzar a usar el iterador j y si i no es igual a j , y el elemento en j es un factor del elemento en i , entonces actualice dp[i] += dp[j] .
- Nuevamente, recorra el mapa y actualice cnt como cnt += dp[i] .
- Después de los pasos anteriores, imprima el valor de cnt 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 mod 1000000007
using namespace std;
// Function that counts subsets whose
// every element is divisible by the
// previous adjacent element
void countSets(int* arr, int n)
{
// Declare a map
map<int, int> dp;
// Initialise dp[arr[i]] with 1
for (int i = 0; i < n; i++)
dp[arr[i]] = 1;
// Traverse the map till end
map<int, int>::iterator i = dp.begin();
for (; i != dp.end(); i++) {
// Traverse the map from i to
// begin using iterator j
map<int, int>::iterator j = i;
for (; j != dp.begin(); j--) {
if (i == j)
continue;
// Check if condition is true
if (i->first % j->first == 0) {
// If factor found, append
// i at to all subsets
i->second
= (i->second % mod
+ j->second % mod)
% mod;
}
}
// Check for the first element
// of the map
if (i != j
&& i->first % j->first == 0) {
i->second
= (i->second % mod
+ j->second % mod)
% mod;
}
}
// Store count of required subsets
int cnt = 0;
// Traverse the map
for (i = dp.begin(); i != dp.end(); i++)
// Update the cnt variable
cnt = (cnt % mod
+ i->second % mod)
% mod;
// Print the result
cout << cnt % mod;
}
// Driver Code
int main()
{
int arr[] = { 16, 18, 6, 7, 2, 19, 20, 9 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
countSets(arr, N);
return 0;
}
Producción:
15
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque Eficiente: Para optimizar el enfoque anterior, la idea es utilizar el concepto similar al Tamiz de Eratóstenes . Siga los pasos a continuación para resolver el problema:
- Cree un tamiz de array [] del elemento de mayor tamaño en la array (digamos maxE ), arr [] e inicialice con 0s .
- Establezca sieve[i] = 1 donde i son los elementos de la array.
- Atraviese la array sieve[] sobre el rango [1, maxE] usando la variable i y si el valor de sieve[i] es positivo, agregue sieve[i] a todos los múltiplos de i (digamos j) si sieve[ j] es positivo.
- Después de completar los pasos anteriores, imprima la suma de los elementos de la array sieve[] 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 mod 1000000007
using namespace std;
// Function to find number of subsets
// satisfying the given condition
void countSets(int* arr, int n)
{
// Stores number of required sets
int cnt = 0;
// Stores maximum element of arr[]
// that defines the size of sieve
int maxE = -1;
// Iterate through the arr[]
for (int i = 0; i < n; i++) {
// If current element > maxE,
// then update maxE
if (maxE < arr[i])
maxE = arr[i];
}
// Declare an array sieve of size N + 1
int* sieve = new int[maxE + 1];
// Initialize with all 0s
for (int i = 0; i <= maxE; i++)
sieve[i] = 0;
// Mark all elements corresponding in
// the array, by one as there will
// always exists a singleton set
for (int i = 0; i < n; i++)
sieve[arr[i]] = 1;
// Iterate from range [1, N]
for (int i = 1; i <= maxE; i++) {
// If element is present in array
if (sieve[i] != 0) {
// Traverse through all its
// multiples <= n
for (int j = i * 2; j <= maxE; j += i) {
// Update them if they
// are present in array
if (sieve[j] != 0)
sieve[j] = (sieve[j] + sieve[i])
% mod;
}
}
}
// Iterate from the range [1, N]
for (int i = 0; i <= maxE; i++)
// Update the value of cnt
cnt = (cnt % mod + sieve[i] % mod) % mod;
delete[] sieve;
// Print the result
cout << cnt % mod;
}
// Driver Code
int main()
{
int arr[] = { 16, 18, 6, 7, 2, 19, 20, 9 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
countSets(arr, N);
return 0;
}
Java
// Java Program to implement
// the above approach
import java.io.*;
import java.util.*;
class GFG {
static int mod = 1000000007;
// Function to find number of subsets
// satisfying the given condition
static void countSets(int arr[], int n)
{
// Stores number of required sets
int cnt = 0;
// Stores maximum element of arr[]
// that defines the size of sieve
int maxE = -1;
// Iterate through the arr[]
for (int i = 0; i < n; i++) {
// If current element > maxE,
// then update maxE
if (maxE < arr[i])
maxE = arr[i];
}
// Declare an array sieve of size N + 1
int sieve[] = new int[maxE + 1];
// Mark all elements corresponding in
// the array, by one as there will
// always exists a singleton set
for (int i = 0; i < n; i++)
sieve[arr[i]] = 1;
// Iterate from range [1, N]
for (int i = 1; i <= maxE; i++) {
// If element is present in array
if (sieve[i] != 0) {
// Traverse through all its
// multiples <= n
for (int j = i * 2; j <= maxE; j += i) {
// Update them if they
// are present in array
if (sieve[j] != 0)
sieve[j]
= (sieve[j] + sieve[i]) % mod;
}
}
}
// Iterate from the range [1, N]
for (int i = 0; i <= maxE; i++)
// Update the value of cnt
cnt = (cnt % mod + sieve[i] % mod) % mod;
// Print the result
System.out.println(cnt % mod);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 16, 18, 6, 7, 2, 19, 20, 9 };
int N = arr.length;
// Function Call
countSets(arr, N);
}
}
// This code is contributed by Kingash.
Python3
#mod 1000000007 # Function to find number of subsets # satisfying the given condition def countSets(arr, n): # Stores number of required sets cnt = 0 # Stores maximum element of arr[] # that defines the size of sieve maxE = -1 # Iterate through the arr[] for i in range(n): # If current element > maxE, # then update maxE if (maxE < arr[i]): maxE = arr[i] # Declare an array sieve of size N + 1 sieve = [0]*(maxE + 1) # Mark all elements corresponding in # the array, by one as there will # always exists a singleton set for i in range(n): sieve[arr[i]] = 1 # Iterate from range [1, N] for i in range(1, maxE + 1): # If element is present in array if (sieve[i] != 0): # Traverse through all its # multiples <= n for j in range(i * 2, maxE + 1, i): # Update them if they # are present in array if (sieve[j] != 0): sieve[j] = (sieve[j] + sieve[i])% 1000000007 # Iterate from the range [1, N] for i in range(maxE + 1): # Update the value of cnt cnt = (cnt % 1000000007 + sieve[i] % 1000000007) % 1000000007 #delete[] sieve # Print the result print (cnt % 1000000007) # Driver Code if __name__ == '__main__': arr =[16, 18, 6, 7, 2, 19, 20, 9] N = len(arr) # Function Call countSets(arr, N) # This code is contributed by mohit kumar 29.
C#
// C# Program to implement
// the above approach
using System;
class GFG {
static int mod = 1000000007;
// Function to find number of subsets
// satisfying the given condition
static void countSets(int[] arr, int n)
{
// Stores number of required sets
int cnt = 0;
// Stores maximum element of arr[]
// that defines the size of sieve
int maxE = -1;
// Iterate through the arr[]
for (int i = 0; i < n; i++) {
// If current element > maxE,
// then update maxE
if (maxE < arr[i])
maxE = arr[i];
}
// Declare an array sieve of size N + 1
int[] sieve = new int[maxE + 1];
// Mark all elements corresponding in
// the array, by one as there will
// always exists a singleton set
for (int i = 0; i < n; i++)
sieve[arr[i]] = 1;
// Iterate from range [1, N]
for (int i = 1; i <= maxE; i++) {
// If element is present in array
if (sieve[i] != 0) {
// Traverse through all its
// multiples <= n
for (int j = i * 2; j <= maxE; j += i) {
// Update them if they
// are present in array
if (sieve[j] != 0)
sieve[j]
= (sieve[j] + sieve[i]) % mod;
}
}
}
// Iterate from the range [1, N]
for (int i = 0; i <= maxE; i++)
// Update the value of cnt
cnt = (cnt % mod + sieve[i] % mod) % mod;
// Print the result
Console.WriteLine(cnt % mod);
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 16, 18, 6, 7, 2, 19, 20, 9 };
int N = arr.Length;
// Function Call
countSets(arr, N);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript Program to implement
// the above approach
let mod = 1000000007;
// Function to find number of subsets
// satisfying the given condition
function countSets(arr,n)
{
// Stores number of required sets
let cnt = 0;
// Stores maximum element of arr[]
// that defines the size of sieve
let maxE = -1;
// Iterate through the arr[]
for (let i = 0; i < n; i++) {
// If current element > maxE,
// then update maxE
if (maxE < arr[i])
maxE = arr[i];
}
// Declare an array sieve of size N + 1
let sieve = new Array(maxE + 1);
for(let i=0;i<maxE + 1;i++)
{
sieve[i]=0;
}
// Mark all elements corresponding in
// the array, by one as there will
// always exists a singleton set
for (let i = 0; i < n; i++)
sieve[arr[i]] = 1;
// Iterate from range [1, N]
for (let i = 1; i <= maxE; i++) {
// If element is present in array
if (sieve[i] != 0) {
// Traverse through all its
// multiples <= n
for (let j = i * 2; j <= maxE; j += i) {
// Update them if they
// are present in array
if (sieve[j] != 0)
sieve[j]
= (sieve[j] + sieve[i]) % mod;
}
}
}
// Iterate from the range [1, N]
for (let i = 0; i <= maxE; i++)
// Update the value of cnt
cnt = (cnt % mod + sieve[i] % mod) % mod;
// Print the result
document.write(cnt % mod+"<br>");
}
// Driver Code
let arr=[16, 18, 6, 7, 2, 19, 20, 9 ];
let N = arr.length;
// Function Call
countSets(arr, N);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
15
Complejidad de tiempo: O(maxE*log(log (maxE)))
Espacio auxiliar: O(maxE)
Publicación traducida automáticamente
Artículo escrito por roytanisha572 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA