313.super-ugly-number.md

313. Super Ugly Number

We use the same approach as 264. Ugly Number II, but have a general approach for any number of primes.

TODO: Try to understand the different approaches: https://leetcode.com/problems/super-ugly-number/solutions/76291/java-three-methods-23ms-36-ms-58ms-with-heap-performance-explained/

Dynamic Programming

fun nthSuperUglyNumber(n: Int, primes: IntArray): Int {
    val pointers = IntArray(primes.size) { 1 }
    val dp = LongArray(n + 1)
    dp[1] = 1L
    for (i in 2..n) {
        var min = Long.MAX_VALUE
        for (j in primes.indices) {
            min = minOf(min, dp[pointers[j]] * 1L * primes[j])
        }
        dp[i] = min
        for (j in primes.indices) {
            if (dp[i] == dp[pointers[j]] * 1L * primes[j]) {
                pointers[j]++
            }
        }
    }
    return dp[n].toInt()
}

Heap

class Solution {
    fun nthSuperUglyNumber(n: Int, primes: IntArray): Int {
        var ans = 1L
        val minHeap = PriorityQueue<Long>()
        val visited = HashSet<Long>()
        minHeap.add(ans)
        visited.add(ans)
        for (i in 0 until n) {
            ans = minHeap.poll()
            for (prime in primes) {
                val next = ans * prime.toLong()
                if (next !in visited) {
                    minHeap.add(next)
                    visited.add(next)
                }
            }      
        }
        return ans.toInt()
    }

}