313. Super Ugly Number.md

313. Super Ugly Number

Question

Write a program to find the nth super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k.

Example:

Input: n = 12, primes = [2,7,13,19]
Output: 32
Explanation: [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.

Thinking:

• Method 1:
  • 参考Ugly number II

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

Second time

1. This question is very similar to ugly number, only difference is that the prime array is dynamic, so we need to add several for-loops for finding the minimum facter and updating the index and factors.

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