Q136: The Ugly Numbers

// Accepted !! Do benefit from the discussion board ~~ Math is really important~~

#include<iostream>
#include<cstdlib>

using namespace std;

const int INF = 1000000000;

int main(int argc, char *argv[])
{
    int ugly[1500];
    ugly[0] = 1;
    for(int i = 1; i < 1500; i++)
    {
        ugly[i] = INF;
        for(int j = 0; j < i; j++)
        {
            if(ugly[j]*2 > ugly[i-1])
            {
                if(ugly[j]*2 < ugly[i])
                    ugly[i] = ugly[j]*2;
            }
            else if(ugly[j]*3 > ugly[i-1])
            {
                if(ugly[j]*3 < ugly[i])
                    ugly[i] = ugly[j]*3;
            }
            else if(ugly[j]*5 > ugly[i-1])
            {
                if(ugly[j]*5 < ugly[i])
                    ugly[i] = ugly[j]*5;
            }
        }
    }
    cout << "The 1500'th ugly number is " << ugly[1499] << ".\n";
    system("PAUSE");
    return EXIT_SUCCESS;
}

// My not-efficient way of solving problem 136

// right answer but cost too much time

#include<iostream>
#include<cstdlib>

using namespace std;

int main(int argc, char *argv[])
{
    int a;
    int index = 1;
    int n[1600];

    for(int i =1 ;; i++)
    {
        a = i;
        while(i % 2 == 0)
        {
            i = i / 2;
        }

        while(i % 3 == 0)
        {
            i = i / 3;
        }

        while(i % 5 == 0)
        {
            i = i / 5;
        }
        if(i == 1)
            n[index++] = a;
        if(index == 1501)
            break;
        i = a;
    }
    cout << "The 1500'th ugly number is " << n[1500] << ".";
    system("PAUSE");
    return EXIT_SUCCESS;
}

Advertisement