<p>An <strong>ugly number</strong> is a positive integer whose prime factors are limited to <code>2</code>, <code>3</code>, and <code>5</code>.</p>

<p>Given an integer <code>n</code>, return <em>the</em> <code>n<sup>th</sup></code> <em><strong>ugly number</strong></em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 10
<strong>Output:</strong> 12
<strong>Explanation:</strong> [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> 1
<strong>Explanation:</strong> 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 1690</code></li>
</ul>

typedef struct {
    uint val;
    uint cur;
    uint potential[3];
} ugly;

class Solution {
    vector <ugly> sequence;
    uint current_l1;
    uint cur_ugly;
public:
    ugly create_ugly(uint n) {
        ugly a;
        a.val = n;
        a.cur = 0;
        a.potential[0] = n*2;
        a.potential[1] = n*3;
        a.potential[2] = n*5;
        return a;
    }
    uint find_min(uint l1) {
        /*
        if (sequence[l1].potential[sequence[l1].cur] <= sequence[l2].potential[sequence[l2].cur]) {
            if (sequence[l1].potential[sequence[l1].cur] <= sequence[l3].potential[sequence[l3].cur]) {
                return l1;
            } else {
                return l3;
            }
        } else {
            if (sequence[l2].potential[sequence[l2].cur] <= sequence[l3].potential[sequence[l3].cur]) {
                return l2;
            } else {
                return l3;
            }
        }*/
        uint i = l1;
        uint min = l1;
        bool flag = true;
        while (flag) {
            if (sequence[i].cur == 0) {
                flag = false;
            }
            if (sequence[i].potential[sequence[i].cur] <= cur_ugly){
                sequence[i].cur++;
            }
            if (sequence[min].potential[sequence[min].cur] > sequence[i].potential[sequence[i].cur]) {
                min = i;
            }
            i++;
            //cout << "\ni = "<< i <<", val = "<<sequence[i].val << ", cur = "<<sequence[i].cur << "min"<<sequence[min].val;
        }
        return min;
    }

    void recal_l1 () {        
        /*for (uint i = current_l1; i <= current_l1 + 2; i++) {
            cout << "\n QweQwe : i " << i << "cur " << sequence[i].cur << " val "<< sequence[i].val <<" val at cur " <<  sequence[i].potential[sequence[i].cur] <<" cur_ugly" << cur_ugly;
            if (sequence[i].potential[sequence[i].cur] == cur_ugly) {
                if (sequence[i].cur == 2) {
                    current_l1++;
                    continue;
                } else {
                    sequence[i].cur++;
                }
            }
        }*/
        if (sequence[current_l1].cur == 2 && sequence[current_l1].potential[sequence[current_l1].cur] == cur_ugly) {
            current_l1++;
        }
        bool flag = true;
        uint i = current_l1;
        while (flag) {
            if (sequence[i].potential[sequence[i].cur] <= cur_ugly) {
                sequence[i].cur++;
            }
            if (sequence[i].cur == 0) {
                flag = false;
            }
            i++;
        }
    }
    uint nthUglyNumber(uint n) {
        switch (n){
            case 0 :
                return 0;
            case 1 :
                return 1;
            case 2 :
                return 2;
            case 3 :
                return 3;
        }
        ugly def1 = create_ugly(1);
        def1.cur = 2;
        ugly def2 = create_ugly(2);
        def2.cur = 1;
        ugly def3 = create_ugly(3);
        ugly def4 = create_ugly(4);

        sequence.push_back(def1);
        sequence.push_back(def2);
        sequence.push_back(def3);
        sequence.push_back(def4); 

        uint prev = 0;
        current_l1 = 0;
        cur_ugly = 4;
        for (uint i = 3; i < n -1; i++) {
            uint choice = find_min(current_l1);
            cur_ugly = sequence[choice].potential[sequence[choice].cur];
  //          cout<<"\nCur_ugly "<<cur_ugly << " choice "<<choice <<" cur " << sequence[choice].cur;
            ugly temp = create_ugly(cur_ugly);
            sequence.push_back(temp);
            recal_l1();            
        }
        return cur_ugly;       
    }
};
23353