Número de subconjuntos con producto menor que k

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 ⁿ 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 ⁿ ). 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:

1. Divide la array en dos partes iguales.
2. 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.
3. Ordene ambos vectores nuevos que contienen productos de elementos para cada subconjunto posible.
4. 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

Producción:

15