Question

Formatted question description: https://leetcode.ca/all/313.html

 313	Super Ugly Number

 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.


 Note:
    1 is a super ugly number for any given primes.
    The given numbers in primes are in ascending order.
    0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.
    The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

 @tag-array

Algorithm

Use an idx array to save the current position, and then we take a number from each prime-sub-chain, find the minimum value, and update the corresponding position of the idx array. Note that there may be more than one minimum value. Update the positions of all the minimum values.

Code

Java

import java.util.ArrayList;
import java.util.List;

public class Super_Ugly_Number {

    public static void main(String[] args) {
        Super_Ugly_Number out = new Super_Ugly_Number();
        Solution s = out.new Solution();

        System.out.println(s.nthSuperUglyNumber(12, new int[]{2,7,13,19}));
    }


    class Solution {
        public int nthSuperUglyNumber(int n, int[] primes) {

            if (n <= 0 || primes == null) {
                return 0;
            }

            List<Integer> nums = new ArrayList<>();
            nums.add(1);

            int[] index = new int[primes.length]; // @note: idx[i] meaning for primes[i], its count to *

            while (nums.size() < n) {

                int minv = Integer.MAX_VALUE;
                for (int i = 0; i < primes.length; i++) {
                    minv = Math.min(minv, primes[i] * nums.get(index[i]));
                }
                nums.add(minv);

                for (int i = 0; i < primes.length; i++) {
                    if (primes[i] * nums.get(index[i]) == minv) {
                        index[i]++;
                    }
                }
            }

            return nums.get(nums.size() - 1);
        }
    }
}

All Problems

All Solutions