LeetCode 264: Ugly Number II

https://leetcode.com/problems/ugly-number-ii/description/

Notes:

This is a very good question. I think this question can be a good interview question for checking rationalization and categorizing. The idea is also using a some dp-like method.

The first step is that, all the ugly number can be written as: 2^a*3^b*5^c. The first one is 1 when a = b = c = 0.

The naive way is straightforward, which checks each number to see whether it is valid or not until we find the nth one. But it is very inefficient since the density is low. (like find the 1 millionth prime number.)

Let us look at the second element: it should be the min(1*2, 1*3, 1*5). So some key observations are

1): the new element must be the existing elements time 2, or 3, or 5;

2): or each existing element can time 2, or 3, or 5, to form the 3 new elements. However, they may not be the next 3 new elements in value;

3): In order to find the next new element in value, we need to find the smallest one among all the potential new elements;

4): Apparently,  if one existing element has formed a new element by timing 2, it can only time 3 or 5 for newer elements. Or it can only time 2, or 3, or 5 one time. (Then it is the new formed elements' turn for forming even newer ones);

5): If one existing element has not been timed by 2, then we should start with 2, since it is the smallest one from this element;

Based on the above analysis, we need three indexes to record the current positions of the elements that can time 2, or 3, or 5. For example, once one existing element times 2, we need to move the index for time 2 by 1, indicating the position of the next element can time 2. Similar functions to the the rest two indexes for 3 and 5.

See the code below:

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> v(1, 1);
        int a = 0, b = 0, c = 0;
        while(v.size() < n) {
            int t1 = v[a]*2, t2 = v[b]*3, t3 = v[c]*5, t = min(t1, min(t2, t3));
            if(t==t1) ++a;//cannot use else. for example 6, we need to update both indexes for 2 and 3
            if(t==t2) ++b;
            if(t==t3) ++c;
            v.push_back(t);
        }
        return v.back();
    }
};