# 264. Ugly Number II

[ **264. Ugly Number II**](https://leetcode.com/problems/ugly-number-ii/description/)

Write a program to find the `n`-th ugly number.

Ugly numbers are **positive numbers** whose prime factors only include `2, 3, 5`.&#x20;

**Example:**

```
Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
```

**Note:**&#x20;

1. `1` is typically treated as an ugly number.
2. `n` **does not exceed 1690**.

***My Solutions:***

建立一个长度为n的数组nums。把2的倍数index2， 3的倍数index3，和5的倍数index5都设置为0。这些index代表由2/3/5乘以index之前，数字在nums中的index。必须要用nums里的数字和2/3/5相乘，这样产出的新数字只会被2/3/5整除。

nums的index = 0时数字是1，之后的每一位，找到2，3，5倍数后最小数。必须用num里已经有的数字乘以

0\. nums=\[1]

1. `starts = [0,0,0]` for numbers `2,3,5`, so `new_num = min(1*2,1*3,1*5) = 2`, and now `starts = [1,0,0]`, `Numbers = [1,2]`.
2. `starts = [1,0,0]`, so `new_num = min(2*2,1*3,1*5) = 3`, and now `starts = [1,1,0]`, `Numbers = [1,2,3]`.
3. `starts = [1,1,0]`, so `new_num = min(2*2,2*3,1*5) = 4`, so now `starts = [2,1,0]`, `Numbers = [1,2,3,4]`.
4. `starts = [2,1,0]`, so `new_num = min(3*2,2*3,1*5) = 5`, so now `starts = [2,1,1]`, `Numbers = [1,2,3,4,5]`.
5. `starts = [2,1,1]`, so `new_num = min(3*2,2*3,2*5) = 6`, so let us be carefull in this case: we need to increase two numbers from `start`, because our new number `6` can be divided both by `2` and `3`, so now `starts = [3,2,1]`, `Numbers = [1,2,3,4,5,6]`.
6. `starts = [3,2,1]`, so `new_num = min(4*2,3*3,2*5) = 8`, so now `starts = [4,2,1]`, `Numbers = [1,2,3,4,5,6,8]`
7. `starts = [4,2,1]`, so `new_num = min(5*2,3*3,2*5) = 9`, so now `starts = [4,3,1]`, `Numbers = [1,2,3,4,5,6,8,9]`.
8. `starts = [4,3,1]`, so `new_num = min(5*2,4*3,2*5) = 10`, so we need to update two elements from `starts` and now `starts = [5,3,2]`, `Numbers = [1,2,3,4,5,6,8,9,10]`
9. `starts = [5,3,2]`, so `new_num = min(6*2,4*3,3*5) = 12`, we again need to update two elements from `starts`, and now `starts = [6,4,2]`, `Numbers = [1,2,3,4,5,6,8,9,10,12]`.
10. `starts = [6,4,2]`, so `new_num = min(8*2,5*3,3*5) = 15`, we again need to update two elements from `starts`, and now `starts = [6,5,3]`, `Numbers = [1,2,3,4,5,6,8,9,10,12,15]`.

```
class Solution {
    public int nthUglyNumber(int n) {
        int[] nums = new int[n];
        nums[0] = 1;
        int index2 = 0, index3 = 0, index5 = 0;
        for (int i = 1; i < n; i++) {
            nums[i] = Math.min(Math.min(nums[index2] * 2, nums[index3] * 3), nums[index5] * 5);
            if (nums[i] == nums[index2] * 2) index2++;
            if (nums[i] == nums[index3] * 3) index3++;
            if (nums[i] == nums[index5] * 5) index5++;
            
        }
        return nums[n - 1];
    }
}
```
