C++/DP solution but we have to use long instead of int


  • 0
    A
    int nthUglyNumber(int n) 
    {
        vector<long> ugly_nums = {1};
        ugly_nums.reserve(n);
        size_t created = 1;
        size_t initial_gen = 0;
        size_t i = 0;
        long candidate,candidate_aux;
    
        while(created < n)
        {
            candidate = LONG_MAX;
            for (i=initial_gen;i<created;++i)
            {
    
                candidate_aux = 2*ugly_nums[i];
                if (candidate_aux > candidate) break;
                if (candidate_aux < candidate && candidate_aux > ugly_nums[created-1])
                {
                    candidate = candidate_aux;
                    continue;
                }
                candidate_aux = 3*ugly_nums[i];
                if (candidate_aux < candidate && candidate_aux > ugly_nums[created-1])
                {
                    candidate = candidate_aux;
                    continue;
                }
                candidate_aux = 5*ugly_nums[i];
                if (candidate_aux < candidate && candidate_aux > ugly_nums[created-1])
                {
                    candidate = candidate_aux;
                    continue;
                }
            }
            ++created;
            ugly_nums.push_back(candidate);
            if (5*ugly_nums[initial_gen] < ugly_nums[created-1]) initial_gen++;
        }
        return ugly_nums[n-1];
    }

Log in to reply
 

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