Precompute all the ugly numbers to make a inquiry list


  • 0
    B

    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;
    };

Log in to reply
 

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