leetcode Question: Ugly Number II

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.

So given current ugly number sequence, e.g., 1, 2, 3, we have to figure out which ugly number is used to generate the next ugly number.  It is not hard to find out, the minimum number in [1x2, 1x3, 1x5, 2x2, 2x3, 2x5, 3x2, 3x3, 3x5], but not in current result should be the next ugly number. However, it is not efficient to compute these values every time, and the "not in current result" condition seems annoying .

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]