Saturday, December 17, 2016

Finding nth ugly number in C++


Ugly Numbers


Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
shows the first 11 ugly numbers. By convention, 1 is included.
Write a program to find and print the 150’th ugly number.

#include <iostream>
#include <vector>
using namespace std;

int find_ugly(int n)
{
    int i2 = 0, i3 = 0, i5 = 0;
    int multiple_2, multiple_3, multiple_5;
 
    vector<int> ugly;
    vector<int> :: iterator it ;
    ugly.push_back(1);
    multiple_5 = ugly[i5]*5;
    multiple_2 = ugly[i2]*2;
    multiple_3 = ugly[i3]*3;
    for (int i=1; i<n; i++) {
        if (multiple_2 < multiple_3) {
            if (multiple_2 < multiple_5) {
                ugly.push_back(multiple_2); i2++;
            } else {
                ugly.push_back(multiple_5); i5++;
            }
        } else {
            if (multiple_3 < multiple_5) {
                ugly.push_back(multiple_3); i3++;
            } else {
                ugly.push_back(multiple_5); i5++;
            }
        }
     
        multiple_5 = ugly[i5]*5;
        while (multiple_5 == multiple_2 || multiple_5 == multiple_3) {
            i5++;
            multiple_5 = ugly[i5]*5;
        }
     
        multiple_2 = ugly[i2]*2;
        while (multiple_3 == multiple_2 || multiple_5 == multiple_2) {
            i2++;
            multiple_2 = ugly[i2]*5;
        }
     
        multiple_3 = ugly[i3]*3;
        while (multiple_3 == multiple_2 || multiple_5 == multiple_3) {
            i3++;
            multiple_3 = ugly[i3]*5;
        }
        cout<<"loop = "<<i<<" i2 = "<<i2<<" i3 = "<<i3<<" i5 = "<< i5<<" multiple_2 = "<<multiple_2<<" multiple_3 = "<<multiple_3<<" multiple_5 = "<< multiple_5<<endl;
    }
    for (it = ugly.begin(); it != ugly.end(); ++it)
        cout << *it << "\t";
    cout<<endl;  
    return ugly[n -1];
}

int main() {
// your code goes here
    cout<<find_ugly(150);
return 0;
}

No comments:

Post a Comment