# 264. Ugly Number II

![](/files/-Ml5jZW1M5XIfh_Jit2x)

<https://www.jiuzhang.com/problem/ugly-number-ii/>

## Solution 1

### use minHeap

從小到大從 minheap 取數字出來

注意, heap 如果不用 long, 數字太大時是會錯的, 會超出int 範圍, 可能結果還會失去 sign 的符號變負的

![](/files/ctD1l1xxDAGwicJc9LXf)

![](/files/QpTKJew47F6ACHzmFYhN)

time: O(3nlog3n)

space: O(3n)

```java
class Solution {
    public int nthUglyNumber(int n) {
        PriorityQueue<Long> minHeap = new PriorityQueue<>();
        minHeap.offer(1L);
        Set<Long> set = new HashSet<>();
        set.add(1L);
        
        int primeFactor[] = new int[]{2,3,5};
        
        Long currUglyNum = 1L;
        for (int i = 0; i < n ; i++) { // 0~9, 9 is 10th
            currUglyNum = minHeap.poll();
            for (int factor : primeFactor) {
                Long newUglyNum = currUglyNum*factor;
                if (!set.contains(newUglyNum)) {
                    set.add(newUglyNum);
                    minHeap.offer(newUglyNum);
                }
            }
        }
        return currUglyNum.intValue();
    }
}
```

or like this, 10th = 0\~(10-1-1) 0\~8, at lasyt return index 9

```
    for (int i = 0; i < n-1; i++) { 
        long cur = heap.poll();
        for (int f : factor) {
            long newCur = cur*f;
            if (!set.contains(newCur)) {
                set.add(newCur);
                heap.offer(newCur);
            }
        }
    }
    return heap.poll().intValue();
```

#### min heap

time: O(3nlog3n)

space: O(3n)

```java
class Solution {
    public int nthUglyNumber(int n) {
        Queue<Long> pq = new PriorityQueue<>();
        pq.offer(1l);

        int count = 0;
        while (!pq.isEmpty()) {
            long cur = pq.poll();
            while (!pq.isEmpty() && pq.peek() == cur) { // 塞入的數可能會有一樣的 ex: 6, 6
                pq.poll(); // 所以一樣的都要排掉
            }
            count++;
            if (count == n) {
                return (int)cur;
            }
            pq.offer(cur*2);
            pq.offer(cur*3);
            pq.offer(cur*5);
        }
        return -1;
    }
}
```

##

## 類似 DP

Ｔ: O(3N) = O(N)

S: O(N)

````java
```java
class Solution {
    public int nthUglyNumber(int n) {
        int i = 0;
        int j = 0;
        int k = 0;

        List<Integer> result = new ArrayList<>();
        result.add(1);
        for (int t = 0; t < n-1; t++) { // n-1 次, 因為已經有一個1加入了
            // 這樣的做法就像是取代了pq, 每次只拿最小的出來(但3個候選人而已, 所以 T: O(3N), 變成線性的解法了)
            int cur = Math.min(Math.min(result.get(i)*2, result.get(j)*3), result.get(k)*5);
            result.add(cur);
            // 跟之前一樣, 一樣的要跳過, 所以 index++, result目的除了結果, 還會存 old ugly number , 之後就可以*2. *3. *5 去得到新的 ugly number
            if (result.get(i)*2 == cur) {
                i++;
            }
            if (result.get(j)*3 == cur) {
                j++;
            }
            if (result.get(k)*5 == cur) {
                k++;
            }
        }
        return result.get(result.size()-1);
    }
}
```
````

## better explain:

<pre class="language-java"><code class="lang-java">class Solution {
    public int nthUglyNumber(int n) {
        List&#x3C;Integer> result = new ArrayList&#x3C;>();
        result.add(1);
        int i = 0, j = 0, k = 0;
        for (int t = 0; t &#x3C; n-1;t++) { // 0
            int cur = Math.min(Math.min(result.get(i)*2, result.get(j)*3), result.get(k)*5);
            result.add(cur);
            if (result.get(i)*2 == cur) { // duplicated
                i++; // 1 -> become result.get(1) this is what we just add in res [1,2]
                // next round use 2, 2*2, 2*3, 2*5] add to min(2*2, 3, 5), get min is 3, result = [1,2,3]
                // next round use  min(2*2, 2*3, 5), get min is 4, result = [1,2,3, 4]
                // i -> 1 to 2
                // next round use  min(3*2, 2*3, 5), get min is 5, result = [1,2,3, 4, 5]
                // k -> 0 to 1
                // next round use  min(3*2, 2*3, 2*5), get min is 6, result = [1,2,3, 4, 5, 6]
                // i -> 2 to 3, j -> 1 to 2
                // next round use  min(4*2, 3*3, 2*5), get min is 8, result = [1,2,3, 4, 5, 6, 8]
                // ... anyway this means prime is unchange, but we move the result_idx to generate non-duplicated number
            }
            if (result.get(j)*3 == cur) {
                j++; // 0 -> 1
            }
            if (result.get(k)*5 == cur) {
                k++; // 0 -> 1
            }
        }
        return result.get(result.size()-1);
    }
}
<strong>
</strong><strong>```java
</strong>/**
T: O(3n)
S: O(n)

[2,3,5]
  1
       2        3          5
4 6 10       6   9  15    10,15,25

8 12 20  12 18 30 ...

[1, 2, 3, 4, 5, 6, 8, 9, 10, 12]

have to skip these duplicated number
pointers to record where is these duplicated number we have use

*5   k                  
*3   j                 
*2   i               
res  1

process:

*5     k                  
*3       j                 
*2         i               
res  1 2 3 4 5 6 ...
res = [1]
start from res = 1 to multiply
 */
```
</code></pre>


---

# 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://timmybeeflin.gitbook.io/cracking-leetcode/dynamic-programming/264.-ugly-number-ii.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.