# Super Ugly Number

<https://leetcode.com/problems/super-ugly-number/description/>

> 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. For example, \[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) 1 is a super ugly number for any given primes.
>
> (2) The given numbers in primes are in ascending order.
>
> (3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes\[i] < 1000.
>
> (4) The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

## Thoughts

和ugly number一个思路，只是这次要维持k个指针，因此用一个数组存储每个指针当前所在的位置。

每次对k个指针找出乘以相应prime最小的数。

## Code

```
class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] f = new int[n];
        f[0] = 1;
        int[] g = new int[primes.length];

        for (int i = 1; i < n; i++) {
            int min = Integer.MAX_VALUE, minIndex = -1;
            for (int j = 0; j < g.length; j++) {
                if (f[g[j]] * primes[j] < min) {
                    minIndex = j;
                    min = f[g[j]] * primes[j];
                }
            }
            g[minIndex]++;

            if (min == f[i - 1]) {
                i--;
            } else {
                f[i] = min;
            }
        }

        return f[n - 1];
    }
}
```

## Analysis

Errors:

1. 丑数可能有重复的
2. 重复时，不应n++, 而应维持i不变

时间复杂度O(nk).

## Ver2.

我们可以把每个指针指向的元素存到min heap中，这样就能理论上O(1)时间找出最小了。总时间为O(nlgk)

```
class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] f = new int[n];
        f[0] = 1;
        PriorityQueue<int[]> pq = new PriorityQueue<>(
            (a, b) -> a[0] - b[0]
        );
        for (int i = 0; i < primes.length; i++) {
            pq.offer(new int[]{f[0] * primes[i], primes[i], 0});
        }

        for (int i = 1; i < n; i++) {
            int[] min = pq.poll();
            if (min[0] == f[i - 1]) {
                i--;
            } else {
                f[i] = min[0];
            }

            pq.offer(new int[]{f[min[2] + 1] * min[1], min[1], min[2] + 1});
        }

        return f[n - 1];
    }
}
```

Errors:\
1\. pq.offer要写到后面，因为现在pointer指向的是下一个要访问的位置，如果不先更新f\[i]则会导致溢出。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/duo-zhi-zhen/super-ugly-number.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.