C++ solution using a single deque.


  • 0
    C

    I keep 3 pointers to figure out which number to generate next in the sequence.

    The part where I pop from the deque is optional. I only did it to reduce space.

    class Solution {
    public:
        int nthUglyNumber(int n) {
            deque<int> uglies = {0, 1, 2, 3};
            if (n <= 0) return 0;
            if (n <= 3) return uglies[n];
            
            int u2p=1, u3p=1, u5p=1; //points to indices
            
            int count = 3;
            int num = 3;
            while (count < n) {
                int cand2 = uglies[u2p] * 2;
                int cand3 = uglies[u3p] * 3;
                int cand5 = uglies[u5p] * 5;
                int newnum;
                if (cand2 <= cand3 && cand2 <= cand5) {
                    newnum = cand2;  u2p++;
                } else if (cand3 <= cand2 && cand3 <= cand5) {
                    newnum = cand3; u3p++;
                } else {
                    newnum = cand5; u5p++;
                }
                if (newnum <= num) continue;
                num = newnum;
                uglies.push_back(num);
                count++;
                
                //optional to reduce space requirement, pop numbers that won't be needed
                int popAmount = std::min(u2p, std::min(u3p, u5p));
                u2p -= popAmount; u3p -= popAmount; u5p -= popAmount;
                while (popAmount != 0) {uglies.pop_front(); popAmount--; } 
            }
            return num;
        }
    };

Log in to reply
 

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