Leetcode Problem 313. Super Ugly Number

313. Super Ugly Number

Leetcode Solutions

Dynamic Programming with Min Heap

  1. Initialize an array dp of size n+1 to store the super ugly numbers, with dp[0] set to 0 and dp[1] set to 1.
  2. Create a min heap q to store potential super ugly numbers along with the prime that generated them and the index of the super ugly number in dp.
  3. Add each prime in primes to the min heap with the initial super ugly number (1) and its index (1).
  4. Loop from i = 2 to n: a. Extract the minimum element cur from the min heap. b. If dp[i-1] is not equal to cur[2] (the potential super ugly number), assign dp[i] to cur[2] and increment i. c. Add a new tuple to the min heap with cur[0] (the prime), cur[1]+1 (the next index), and cur[0]*dp[cur[1]+1] (the next potential super ugly number).
  5. Return dp[n] as the nth super ugly number.
UML Thumbnail

Dynamic Programming with Multiple Pointers

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...