Se le da una array de n elementos, debe encontrar la cantidad de subconjuntos cuyo producto de elementos es menor o igual a un número entero k dado.
Ejemplos:
Input : arr[] = {2, 4, 5, 3}, k = 12 Output : 8 Explanation : All possible subsets whose products are less than 12 are: (2), (4), (5), (3), (2, 4), (2, 5), (2, 3), (4, 3) Input : arr[] = {12, 32, 21 }, k = 1 Output : 0 Explanation : there is not any subset such that product of elements is less than 1
Enfoque: si seguimos el enfoque básico para resolver este problema, entonces tenemos que generar todos los 2 n subconjuntos posibles y para cada uno de ellos tenemos que calcular el producto de los elementos del subconjunto y comparar el valor de los productos con el dado. Pero la desventaja de este enfoque es que su complejidad temporal es demasiado alta, es decir, O(n*2 n ). Ahora, podemos ver que va a ser una complejidad de tiempo exponencial lo que debe evitarse en el caso de codificaciones competitivas.
Enfoque avanzado: vamos a utilizar el concepto de encuentro en el medio. Al utilizar este concepto, podemos reducir la complejidad de nuestro enfoque de O(n*2 n/2 ).
Cómo usar MEET IN THE MIDDLE Enfoque: En primer lugar, simplemente dividimos la array dada en dos partes iguales y luego generamos todos los subconjuntos posibles para ambas partes de la array y almacenamos el valor del producto de los elementos para cada subconjunto por separado en dos vectores (digamos subconjunto1 y subconjunto2). Ahora esto costará una complejidad de tiempo O (2 n/2 ). Ahora, si clasificamos estos dos vectores (subconjunto1 y subconjunto2) que tienen (2 n/2 ) elementos cada uno, esto costará O (2 n/2 *log2 n/2 ) ≈ O(n*(2 n/2 )) Complejidad temporal. En el siguiente paso, atravesamos un subconjunto de vectores 1 con 2 n/2elementos y encuentre el límite superior de k/subset1[i] en el segundo vector que nos dirá el recuento de elementos totales cuyos productos serán menores o iguales que k. Y así, para cada elemento en el subconjunto1, intentaremos realizar una búsqueda binaria en forma de límite_superior en el subconjunto2, lo que nuevamente dará como resultado una complejidad de tiempo de O(n*(2 n/2 ) ) . Entonces, si tratamos de calcular nuestra complejidad general para este enfoque, tendremos O(n*(2 n/2 ) + n*(2 n/2 ) + n*(2 n/2 )) ≈ O(n*(2 n/2 )) como nuestra complejidad de tiempo, que es mucho más eficiente que nuestro enfoque de fuerza bruta.
Algoritmo:
- Divide la array en dos partes iguales.
- Genere todos los subconjuntos y para cada subconjunto calcule el producto de los elementos y empújelo a un vector. intente esto para ambas partes de la array.
- Ordene ambos vectores nuevos que contienen productos de elementos para cada subconjunto posible.
- Recorra cualquier vector y encuentre el límite superior del elemento k/vector[i] para encontrar cuántos subconjuntos hay para el vector[i] cuyo producto de elementos es menor que k.
Algunos puntos clave para mejorar la complejidad:
- Ignora los elementos de la array si son mayores que k.
- Ignore el producto de los elementos para insertar en el vector (subconjunto1 o subconjunto2) si es mayor que k.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP to find the count subset having product // less than k #include <bits/stdc++.h> using namespace std; int findSubset( long long int arr[], int n, long long int k) { // declare four vector for dividing array into // two halves and storing product value of // possible subsets for them vector< long long int > vect1, vect2, subset1, subset2; // ignore element greater than k and divide // array into 2 halves for ( int i = 0; i < n; i++) { // ignore element if greater than k if (arr[i] > k) continue ; if (i <= n / 2) vect1.push_back(arr[i]); else vect2.push_back(arr[i]); } // generate all subsets for 1st half (vect1) for ( int i = 0; i < (1 << vect1.size()); i++) { long long value = 1; for ( int j = 0; j < vect1.size(); j++) { if (i & (1 << j)) value *= vect1[j]; } // push only in case subset product is less // than equal to k if (value <= k) subset1.push_back(value); } // generate all subsets for 2nd half (vect2) for ( int i = 0; i < (1 << vect2.size()); i++) { long long value = 1; for ( int j = 0; j < vect2.size(); j++) { if (i & (1 << j)) value *= vect2[j]; } // push only in case subset product is // less than equal to k if (value <= k) subset2.push_back(value); } // sort subset2 sort(subset2.begin(), subset2.end()); long long count = 0; for ( int i = 0; i < subset1.size(); i++) count += upper_bound(subset2.begin(), subset2.end(), (k / subset1[i])) - subset2.begin(); // for null subset decrement the value of count count--; // return count return count; } // driver program int main() { long long int arr[] = { 4, 2, 3, 6, 5 }; int n = sizeof (arr) / sizeof (arr[0]); long long int k = 25; cout << findSubset(arr, n, k); return 0; } |
Python3
# Python3 to find the count subset # having product less than k import bisect def findSubset(arr, n, k): # declare four vector for dividing # array into two halves and storing # product value of possible subsets # for them vect1, vect2, subset1, subset2 = [], [], [], [] # ignore element greater than k and # divide array into 2 halves for i in range ( 0 , n): # ignore element if greater than k if arr[i] > k: continue if i < = n / / 2 : vect1.append(arr[i]) else : vect2.append(arr[i]) # generate all subsets for 1st half (vect1) for i in range ( 0 , ( 1 << len (vect1))): value = 1 for j in range ( 0 , len (vect1)): if i & ( 1 << j): value * = vect1[j] # push only in case subset product # is less than equal to k if value < = k: subset1.append(value) # generate all subsets for 2nd half (vect2) for i in range ( 0 , ( 1 << len (vect2))): value = 1 for j in range ( 0 , len (vect2)): if i & ( 1 << j): value * = vect2[j] # push only in case subset product # is less than equal to k if value < = k: subset2.append(value) # sort subset2 subset2.sort() count = 0 for i in range ( 0 , len (subset1)): count + = bisect.bisect(subset2, (k / / subset1[i])) # for null subset decrement the # value of count count - = 1 # return count return count # Driver Code if __name__ = = "__main__" : arr = [ 4 , 2 , 3 , 6 , 5 ] n = len (arr) k = 25 print (findSubset(arr, n, k)) # This code is contributed by Rituraj Jain |
15
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA