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 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:

  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
    

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *