## Ugly Number II

Write a program to find the

`n`

-th ugly number.
Ugly numbers are positive numbers whose prime factors only include

`2, 3, 5`

. For example, `1, 2, 3, 4, 5, 6, 8, 9, 10, 12`

is the sequence of the first `10`

ugly numbers.
Note that

`1`

is typically treated as an ugly number.### Analysis:

This problem needs a little thinking about how to generate the next ugly number.From the definition and examples we know that:

- the ugly number u, must come from a previous ugly number times either 2, 3 or 5, e.g., 8 comes from 4 x 2, where 4 is a ugly number.
- the ugly number u[i], may NOT come from u[i-1] x 2, x 3, or x 5, e.g., 10 comes from 2 x 5 (or 5 x 2), but not from its previous ugly number 9.

Therefore, if we could track the values we compute, it becomes much easier to handle the two issues we mentioned.

- Maintain 3 lists, each one stores the ugly number times 2, 3, and 5, respectively.
- Every time, we get the newest ugly number, and update the 3 lists.
- Keep 3 pointers (say p1, p2, and p3) for the 3 lists, every time just select the min(L1[p1], L2[p2], L3[p3]) as the new ugly number, and update the corresponding pointer.
- When there are more than one minimum values, remember to update all the corresponding pointers.

I have draw the following figure, to illustrate the procedure of the method, in which step 1 to step 3 is the first iteration to generate ugly number 2, and step 4 to step 6 is the 2nd iteration to generate ugly number 3.

###

Code(C++):

class Solution { public: int nthUglyNumber(int n) { vector<int> l1; vector<int> l2; vector<int> l3; vector<int> res(n, 0); l1.push_back(1); l2.push_back(1); l3.push_back(1); res[0] = 1; int i1 = 1; int i2 = 1; int i3 = 1; for (int i=1;i<n;i++){ l1.push_back(res[i-1]*2); l2.push_back(res[i-1]*3); l3.push_back(res[i-1]*5); int tmp = min(l1[i1], min(l2[i2],l3[i3])); if (tmp == l1[i1]) { res[i] = l1[i1++];} if (tmp == l2[i2]) { res[i] = l2[i2++];} if (tmp == l3[i3]) { res[i] = l3[i3++];} } return res[n-1]; } };

### Code(Python):

class Solution(object): def nthUglyNumber(self, n): """ :type n: int :rtype: int """ l1 = [1] l2 = [1] l3 = [1] res = [0 for x in range(n+1)] res[0] = 1 i1 = 1 i2 = 1 i3 = 1 for i in range(n): l1.append(res[i]*2) l2.append(res[i]*3) l3.append(res[i]*5) tmp = min(min(l1[i1], l2[i2]),l3[i3]) if tmp == l1[i1]: res[i+1] = l1[i1] i1+=1 if tmp == l2[i2]: res[i+1] = l2[i2] i2+=1 if tmp == l3[i3]: res[i+1] = l3[i3] i3+=1 return res[-2]

## No comments:

## Post a Comment