# Precompute all the ugly numbers to make a inquiry list

• The number of all the ugly numbers are much fewer than [log(2, MAX_INT)] * [log(3, MAX_INT)] * [log(5, MAX_INT)] = 30 * 19 * 13 = 7410. So we can precompute a list for frequent inquiries.

``````class Solution {
public:
Solution(){
long long inf = 0xffffffff;
vector<long long> fac2, fac3, fac5;
long long fac = 1, ugly = 1;
while(fac <= inf){
fac2.push_back(fac); fac *= 2;
}
fac = 1;
while(fac <= inf){
fac3.push_back(fac); fac *= 3;
}
fac = 1;
while(fac <= inf){
fac5.push_back(fac); fac *= 5;
}
for(int i = 0; i < fac2.size(); i ++) for(int j = 0; j < fac3.size(); j ++){
fac = fac2[i] * fac3[j];
if(fac > inf)break;
for(int k = 0; k < fac5.size(); k ++){
ugly = fac * fac5[k];
if(ugly > inf)break;
uglyNums.push_back(ugly);
}
}
sort(uglyNums.begin(), uglyNums.end());
}

int nthUglyNumber(int n) {
return uglyNums[n - 1];
}
private:
vector<long long> uglyNums;
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.