Ugly Numbers UVA
<p>I am trying to compute the 1500th ugly number from UVA problem set no. 136.</p>

<p>(Ref: <a href="https://uva.onlinejudge.org/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=3&amp;page=show_problem&amp;problem=72" rel="nofollow">https://uva.onlinejudge.org/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=3&amp;page=show_problem&amp;problem=72</a>)</p>

<p>My algorithm is simple:</p>

<ul>
<li>Keep track of all the ugly numbers in an array <em>un</em>.</li>
<li>Let <em>un[i]</em> be the i+1 ugly number.</li>
</ul>

<p>Steps:</p>

<ol>
<li><p>Use a tmp variable <em>cur</em> to hold the index of the <em>ith</em> ugly number.</p></li>
<li><p>Compute <em>un[cur] x 2</em>, <em>un[cur] x 3</em> and <em>un[cur] x 5</em>.</p></li>
<li><p>Eliminate duplicates using a set and store them into <em>un</em></p></li>
<li><p>Sort the array to ensure that <em>un[i+1]</em> will always be the smallest possible.</p></li>
<li><p>Increment the cur variable so that it becomes index of the <em>i+1th</em> ugly number.</p></li>
<li><p>Repeat until 1500 ugly numbers have been generated in the array.</p></li>
</ol>

<p>My code:</p>

<pre><code># include&lt;iostream&gt;
# include&lt;set&gt;
# include&lt;algorithm&gt;

using namespace std;

int main(void) {
    long long un[1500] = { 0 };
    set&lt;long long&gt; us;
    un[0] = 1;
    us.insert(1);
    int i = 1,unE = 0,cur = 0;

    while(true) {
        unE = 0;
        sort(un,un+i);
        if(us.find(un[cur]*2) == us.end()) {
            un[i+unE] = un[cur]*2;
            us.insert(un[i+unE]);
            unE++;
        }
        if(i + unE &gt; 1500 - 1) {
            break;
        }
        if(us.find(un[cur]*3) == us.end()) {
            un[i+unE] = un[cur]*3;
            us.insert(un[i+unE]);
            unE++;
        }
        if(i + unE &gt; 1500 - 1) {
            break;
        }
        if(us.find(un[cur]*5) == us.end()) {
            un[i+unE] = un[cur]*5;
            us.insert(un[i+unE]);
            unE++;
        }
        i+=unE;
        cur++;
    }
    sort(un,un+1500);

    for(int i = 0; i &lt; 1500; i++) {
        cout &lt;&lt; un[i] &lt;&lt; " ";
    }
    cout &lt;&lt; un[1500-1] &lt;&lt; endl;
}
</code></pre>

<p>My algorithm does not output the correct number, which is 859963392. I am getting a bigger number instead. Could someone please point me in the right direction?</p>