Super Ugly Number (Número cuyos factores primos están en un conjunto dado)

Los números súper feos son números positivos cuyos factores primos están todos en la lista de primos dada. Dado un número n, la tarea es encontrar el n-ésimo número súper feo.
Se puede suponer que un conjunto dado de números primos está ordenado. Además, el primer número Super Ugly es 1 por convención.

Ejemplos:  

Input  : primes[] = [2, 5]
         n = 5
Output : 8
Super Ugly numbers with given prime factors 
are 1, 2, 4, 5, 8, ...
Fifth Super Ugly number is 8

Input  : primes[] = [2, 3, 5]
         n = 50
Output : 243

Input : primes[] = [3, 5, 7, 11, 13]
        n = 9
Output: 21 

En nuestra publicación anterior, discutimos el número feo . Este problema es básicamente una extensión de Ugly Numbers .
Una solución simple para este problema es elegir uno por uno cada número comenzando desde 1 y encontrar todos sus factores primos, si todos los factores primos se encuentran en el conjunto dado de primos, eso significa que el número es súper feo. Repite este proceso hasta que obtengamos el enésimo Número Súper Feo.

Una solución eficiente para este problema es similar al Método-2 de Ugly Number . Aquí está el algoritmo:  

1. Sea k el tamaño de una array dada de números primos.
2. Declara un conjunto para números súper feos.
3. Inserta el primer número feo (que siempre es 1) en el conjunto.
4. Inicialice la array multiple_of[k] de tamaño k con 0. Cada elemento de esta array es un iterador para el primo correspondiente en la array primos[k].
5. Inicialice la array nextMultipe[k] con primos[k]. Esta array se comporta como las siguientes variables múltiples de cada número primo en una array dada de primos[k], es decir; nextMultiple[i] = primos[i] * feo[++multiple_of[i]].
6. Ahora repite hasta que haya n elementos en el conjunto feo. 
   a). Encuentre el mínimo entre los múltiplos actuales de números primos en la array nextMultiple[] e insértelo en el conjunto de números feos. 
   b). Luego encuentra que este mínimo actual es múltiplo de cuál primo. 
   C). Aumentar el iterador en 1, es decir; ++multiple_Of[i], para el próximo múltiplo del número primo actual seleccionado y actualice nextMultiple para él.

A continuación se muestra la implementación de los pasos anteriores. 

// C++ program to find n'th Super Ugly number
#include<bits/stdc++.h>
using namespace std;
 
// Function to get the nth super ugly number
// primes[]       --> given list of primes f size k
// ugly           --> set which holds all super ugly
//                    numbers from 1 to n
// k              --> Size of prime[]
int superUgly(int n, int primes[], int k)
{
    // nextMultiple holds multiples of given primes
    vector<int> nextMultiple(primes, primes+k);
 
    // To store iterators of all primes
    int multiple_Of[k];
    memset(multiple_Of, 0, sizeof(multiple_Of));
 
    // Create a set to store super ugly numbers and
    // store first Super ugly number
    set<int> ugly;
    ugly.insert(1);
 
    // loop until there are total n Super ugly numbers
    // in set
    while (ugly.size() != n)
    {
        // Find minimum element among all current
        // multiples of given prime
        int next_ugly_no = *min_element(nextMultiple.begin(),
                                    nextMultiple.end());
 
        // insert this super ugly number in set
        ugly.insert(next_ugly_no);
 
        // loop to find current minimum is multiple
        // of which prime
        for (int j=0; j<k; j++)
        {
            if (next_ugly_no == nextMultiple[j])
            {
                // increase iterator by one for next multiple
                // of current prime
                multiple_Of[j]++;
 
                // this loop is similar to find  dp[++index[j]]
                // it -->  dp[++index[j]]
                set<int>::iterator it = ugly.begin();
                for (int i=1; i<=multiple_Of[j]; i++)
                    it++;
 
                nextMultiple[j] = primes[j] * (*it);
                break;
            }
        }
    }
 
    // n'th super ugly number
    set<int>::iterator it = ugly.end();
    it--;
    return *it;
}
 
/* Driver program to test above functions */
int main()
{
    int primes[] = {2,  5};
    int k = sizeof(primes)/sizeof(primes[0]);
    int n = 5;
    cout << superUgly(n, primes, k);
    return 0;
}

Producción:  

8

Este artículo es una contribución de Shashank Mishra (Gullu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Otro método (usando la cola de prioridad) 
Aquí usamos la cola de prioridad mínima del montón. 
La idea es empujar el primer feo no. que es 1 en la cola de prioridad y en cada iteración toma la parte superior de la cola de prioridad y empuja todos los múltiplos de esa parte superior en la cola de prioridad. 
Suponiendo que a[] = {2, 3, 5}, 
por lo que en la primera iteración 1 es superior, por lo que se extrae 1 y se presiona 1 * 2, 1 * 3, 1 * 5. 
En la segunda iteración, el mínimo es 2, por lo que se extrae y se presiona 2 * 2, 2 * 3, 2 * 5 y así sucesivamente.

Implementación:

// C++ program for super ugly number
#include<bits/stdc++.h>
using namespace std;
// function will return the nth super ugly number
int ugly(int a[], int size, int n){
     
    // n cannot be negative hence
    // return -1 if n is 0 or -ve
    if(n <= 0)
        return -1;
  
    if(n == 1)
        return 1;
     
    // Declare a min heap priority queue
    priority_queue<int, vector<int>, greater<int>> pq;
     
    // Push all the array elements to priority queue
    for(int i = 0; i < size; i++){
        pq.push(a[i]);
    }
     
    // once count = n we return no
    int count = 1, no;
     
    while(count < n){
        // Get the minimum value from priority_queue
        no = pq.top();
        pq.pop();
         
        // If top of pq is no then don't increment count.
        // This to avoid duplicate counting of same no.
        if(no != pq.top())
        {
            count++;
         
            // Push all the multiples of no. to priority_queue
            for(int i = 0; i < size; i++){
                pq.push(no * a[i]);
            // cnt+=1;
        }
        }
    }
    // Return nth super ugly number
    return no;
}
 
/* Driver program to test above functions */
int main(){
    int a[3] = {2, 3,5};
    int size = sizeof(a) / sizeof(a[0]);
    cout << ugly(a, size, 10)<<endl;
    return 0;
}

# Python3 program for super ugly number
 
# function will return the nth super ugly number
def ugly(a, size, n):
 
    # n cannot be negative hence return -1 if n is 0 or -ve
    if(n <= 0):
        return -1
    if(n == 1):
        return 1
 
    # Declare a min heap priority queue
    pq = []
 
    # Push all the array elements to priority queue
    for i  in range(size):
        pq.append(a[i])
 
    # once count = n we return no
    count = 1
    no = 0
    pq = sorted(pq)
 
    while(count < n):
        # sorted(pq)
        # Get the minimum value from priority_queue
        no = pq[0]
        del pq[0]
 
 
        # If top of pq is no then don't increment count.
        # This to avoid duplicate counting of same no.
        if(no != pq[0]):
            count += 1
 
            # Push all the multiples of no. to priority_queue
            for i in range(size):
                pq.append(no * a[i])
            #   cnt+=1
        pq = sorted(pq)
    # Return nth super ugly number
    return no
 
# /* Driver program to test above functions */
if __name__ == '__main__':
    a = [2, 3,5]
    size = len(a)
    print(ugly(a, size, 1000))
 
    # This code is contributed by mohit kumar 29.

<script>
// Javascript program for super ugly number
     
    //function will return the nth super ugly number
    function ugly(a,size,n)
    {
        //n cannot be negative hence return -1 if n is 0 or -ve
    if(n <= 0)
        return -1;
   
    if(n == 1)
        return 1;
      
    // Declare a min heap priority queue
    let pq=[];;
      
    // Push all the array elements to priority queue
    for(let i = 0; i < size; i++){
        pq.push(a[i]);
    }
      
    // once count = n we return no
    let count = 1, no;
    pq.sort(function(a,b){return a-b;}) ;
     
    while(count < n){
        // Get the minimum value from priority_queue
        no = pq.shift();
         
          
        // If top of pq is no then don't increment count. This to avoid duplicate counting of same no.
        if(no != pq[0])
        {
            count++;
          
            //Push all the multiples of no. to priority_queue
            for(let i = 0; i < size; i++){
                pq.push(no * a[i]);
            //    cnt+=1;
        }
         
        }
        pq.sort(function(a,b){return a-b;}) ;
    }
    // Return nth super ugly number
    return no;
    }
     
     
    /* Driver program to test above functions */
    let a=[2, 3,5];
    let size = a.length;
    document.write(ugly(a, size, 1000));
     
     
    // This code is contributed by unknown2108
</script>

Producción: 

51200000

Complejidad de tiempo: O(n*size*logn)
Espacio auxiliar: O(n)
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.