Python: Find the nth super ugly number from a given prime list of size k using Heap queue algorithm

Last update on December 21 2024 07:30:27 (UTC/GMT +8 hours)

Write a Python program to find the nth super ugly number from a given prime list of size k using the heap queue algorithm.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.

Sample Solution:

Python Code:

import heapq
#Ref.: https://bit.ly/32c9P3A
def nth_Super_Ugly_Number(n, primes):
    uglies = [1]

    def gen(prime):
        for ugly in uglies:
            yield ugly * prime

    merged = heapq.merge(*map(gen, primes))
    while len(uglies) < n:
        ugly = next(merged)
        if ugly != uglies[-1]:
            uglies.append(ugly)
    return uglies[-1]
n = 12
primes = [2,7,13,19]
print(nth_Super_Ugly_Number(n, primes))

Sample Output:

32

Flowchart:

Python Code Editor:

Have another way to solve this solution? Contribute your code (and comments) through Disqus.

Previous: Given a n x n matrix where each of the rows and columns are sorted in ascending order, write a Python program to find the kth smallest element in the matrix.
Next: Write a Python program to get the k most frequent elements from a given non-empty list of words using Heap queue algorithm.