Super Ugly Number

Write a program to find the nth super ugly number.

• Time: O(n)
• Space: O(n)

public int nthSuperUglyNumber(int n, int[] primes) {
    int[] count = new int[primes.length];
    int[] dp = new int[primes.length];
    for (int i = 0; i < primes.length; i++) {
        dp[i] = primes[i];
    }
    int[] ret = new int[n];
    ret[0] = 1;
    for (int i = 1; i < n; i++) {
        ret[i] = Integer.MAX_VALUE;
        for (int j = 0; j < primes.length; j++) {
            ret[i] = Math.min(ret[i], dp[j]);
        }
        for (int j = 0; j < primes.length; j++) {
            if (ret[i] == dp[j]) {
                dp[j] = primes[j] * ret[++count[j]];
            }
        }
    }
    return ret[n - 1];
}