Ugly Numbers UVA [closed]

Question

I am trying to compute the 1500th ugly number from UVA problem set no. 136.

(Ref: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=72)

My algorithm is simple:

• Keep track of all the ugly numbers in an array un.
• Let un[i] be the i+1 ugly number.

Steps:

1. Use a tmp variable cur to hold the index of the ith ugly number.

2. Compute un[cur] x 2, un[cur] x 3 and un[cur] x 5.

3. Eliminate duplicates using a set and store them into un

4. Sort the array to ensure that un[i+1] will always be the smallest possible.

5. Increment the cur variable so that it becomes index of the i+1th ugly number.

6. Repeat until 1500 ugly numbers have been generated in the array.

My code:

# include<iostream>
# include<set>
# include<algorithm>

using namespace std;

int main(void) {
    long long un[1500] = { 0 };
    set<long long> 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 > 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 > 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 < 1500; i++) {
        cout << un[i] << " ";
    }
    cout << un[1500-1] << endl;
}

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?

Answer 1

Your algorithm is almost correct, however the error is that you should not stop when 1500 numbers have been generated, but rather when 'curr' reaches the 1500th number. That is so because not all ugly numbers after 'curr' have been generated, you are only sure that you have all ugly numbers before 'curr' at any point. Another suggestion to optimize your algorithm is to use a heap for all numbers after 'curr', that way you don't need to sort the whole array every time and you also don't need to use sets at all. Here is my code:

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
vector<long long> un; //using vector because we don't know how many ugly numbers we will need to generate
//If we decide to use an array (the way you did) it is better to define it outside of main().
priority_queue<long long> nun; //priority queue used for storing the next ugly numbers
const int TARGET=1500; //always good to store magical numbers as constants instead of having them appear all over the code
int main()
{
    un.push_back(1); //adding the first ugly number
    for (int i=0;i<TARGET-1;++i)
    /*
    We have already found the first ugly number (1),
    so we only need to find TARGET-1 more.
    */
    {
        nun.push(-un[i]*2);
        nun.push(-un[i]*3);
        nun.push(-un[i]*5);
        //adding the next ugly numbers to the heap
        /*
        Adding them as negative numbers because priority_queue
        keeps the largest number on the top and we need the smallest.
        */
        while (-nun.top()==un[i])
        {
            nun.pop();
            //removing duplicates
            /*
            We can prove that we will never have more than 3 copies
            of a number in the heap and thus that this will not
            affect the performance.
            1) We will never have more than one copy of a number in un.
            2) Each number can be added to nun in 3 different ways:
            by multiplying a number form un by 2, 3 or 5.
            */
        }
        un.push_back(-nun.top());
        nun.pop();
        //adding the next ugly number to un
    }
    cout<<un[TARGET-1]<<endl;
    /*
    Indexing starts at 0 so the TARGETth number is at index TARGET-1.
    */
    return 0;
}

My program does indeed output 859963392, the correct answer.

After thinking about it a bit, I got it down to linear complexity. Here is the code:

#include<iostream>
#include<vector>
//#include<conio.h>
using namespace std;
vector<long long> un; //using vector because we don't know how many ugly numbers we will need to generate
//If we decide to use an array (the way you did) it is better to define it outside of main().
const int TARGET=1500; //always good to store magical numbers as constants instead of having them appear all over the code
int l2=0,l3=0,l5=0; //store the indexes of the last numbers multiplied by 2, 3 and 5 respectively
int main()
{
    un.push_back(1); //adding the first ugly number
    for (int i=0;i<TARGET-1;++i)
    /*
    We have already found the first ugly number (1),
    so we only need to find TARGET-1 more.
    */
    {
        un.push_back(min(min(un[l2]*2,un[l3]*3),un[l5]*5));
        //adding the next ugly number to un
        if (un[i+1]==un[l2]*2) //checks if 2 multiplied by the number at index l2 has been included in un, if so, increment l2
        {
            ++l2;
        }
        if (un[i+1]==un[l3]*3) //checks if 3 multiplied by the number at index l3 has been included in un, if so, increment l3
        {
            ++l3;
        }
        if (un[i+1]==un[l5]*5) //checks if 5 multiplied by the number at index l5 has been included in un, if so, increment l5
        {
            ++l5;
        }
        /*
        Basically only one of the variables l2, l3 and l5 (the one we used) will be incremented in a cycle unless we can get a number
        in more than one way, in which case incrementing more than one of them is how we avoid duplicates.
        Uncomment the commented code to observe this.
        P.S. @PaulMcKenzie I can deal without a debugger just fine.
        */
        //cerr<<i<<": "<<l2<<"("<<un[l2]*2<<") "<<l3<<"("<<un[l3]*3<<") "<<l5<<"("<<un[l5]*5<<") "<<un[i+1]<<endl;
        //getch();
    }
    cout<<un[TARGET-1]<<endl;
    /*
    Indexing starts at 0 so the TARGETth number is at index TARGET-1.
    */
    return 0;
}

The first solution doesn't even need the vector at all, as it doesn't use the previous numbers. So you can optimize it memorywise by using a single variable. Here is such an implementation:

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
long long un; //last ugly number found
priority_queue<long long> nun; //priority queue used for storing the next ugly numbers
const int TARGET=1500; //always good to store magical numbers as constants instead of having them appear all over the code
int main()
{
    un=1; //adding the first ugly number
    for (int i=0;i<TARGET-1;++i)
    /*
    We have already found the first ugly number (1),
    so we only need to find TARGET-1 more.
    */
    {
        nun.push(-un*2);
        nun.push(-un*3);
        nun.push(-un*5);
        //adding the next ugly numbers to the heap
        /*
        Adding them as negative numbers because priority_queue
        keeps the largest number on the top and we need the smallest.
        */
        while (-nun.top()==un)
        {
            nun.pop();
            //removing duplicates
            /*
            We can prove that we will never have more than 3 copies
            of a number in the heap and thus that this will not
            affect the performance.
            1) We will never have more than one copy of a number in un.
            2) Each number can be added to nun in 3 different ways:
            by multiplying a number form un by 2, 3 or 5.
            */
        }
        un=-nun.top();
        nun.pop();
        //adding the next ugly number to un
    }
    cout<<un<<endl;
    /*
    Indexing starts at 0 so the TARGETth number is at index TARGET-1.
    */
    return 0;
}

We can also optimize the linear solution to use less memory by freeing up the memory behind the minimum of l2, l3 and l5. Note that both the third solution and the optimized version of the second one use sublinear memory as TARGET goes to infinity, since in the limit, almost all ugly numbers are divisible by 2, 3 and 5. Thus on each iteration we move each pointer by one (so the length of un doesn't change) or, in the case of the heap solution, we add 3 numbers to the heap and then pop 3 numbers from the heap (so the size of the heap doesn't change). In fact with more careful analysis we can see that the memory grows like TARGET^(2/3).

Answer 2

A more simple to code but harder to read solution is:

 #include <iostream>

using namespace std;

int main(){
    const int n = 1499;
    int a [ 1500 ];
    int p1(0), p2(0), p3(0), end(0);
    a [ 0 ] = 1;
    while ( end < n ){
        while ( a [ p1 ] * 2 <= a [ end ] )  ++ p1;
        while ( a [ p2 ] * 3 <= a [ end ] )  ++ p2;
        while ( a [ p3 ] * 5 <= a [ end ] )  ++ p3;
        if ( a [ p1 ] * 2 < a [ p2 ] * 3 && a [ p1 ] * 2 < a [ p3 ] * 5 )
            a [ ++ end ] = a [ p1 ++ ] * 2;
        else    if ( a [ p2 ] * 3 < a [ p3 ] * 5 )
                    a [ ++ end ] = a [ p2 ++ ] * 3;
                else    a [ ++ end ] = a [ p3 ++ ] * 5;
    }
    cout << "The 1500'th ugly number is " << a [ end ] << ".\n";
    return 0;
}

For the record
,Bruteforce solution, just checking all numbers for whether they are ugly or not and keeping the count of ugly ones take more than 20 seconds on my computer with following code:

//uva136 preparer  
#include <iostream>

using namespace std;

typedef  long long ll;



bool is_ugly(int in)
{

    while( true)
    {
        if(in % 5 ==0)
            in /= 5;
        else if( in %2==0)
            in /=2 ;
        else if (in % 3 == 0 )
            in/=3;
        else
            break;

    }
    if(in==1)
        return true ;
    else 
        return false ;

}

int main()
{
    int c=0 ; 
    ll j=6;
    int i=6;
    for(j =6;(i<1501) ; j++)
    {
        if(isugly(j))
            i++;
    }
    cout<<j-1<<endl<<double(clock())/CLOCKS_PER_SEC;// because at the last iteration of four , j is updated to j+1 and we should minus it by one to make it no count .
    return 0;
}