29ms C++ solution using queues


  • 0
    V
    class Solution {
    public:
        int nthUglyNumber(int n) {
            if(n == 1) return 1;
            queue<int> qfactor2;
            queue<int> qfactor3;
            queue<int> qfactor5;
            int indFactor2 = 1, indFactor3 = 1, indFactor5 = 1;
            int uglyNum=0;
            for(int i=2; i<=n; i++) {
                uglyNum = min(2*indFactor2, min(3*indFactor3, 5*indFactor5));
                qfactor2.push(uglyNum);
                qfactor3.push(uglyNum);
                qfactor5.push(uglyNum);
                if(uglyNum == 2*indFactor2) {
                    indFactor2 = qfactor2.front();
                    qfactor2.pop();
                } 
                if(uglyNum == 3*indFactor3) {
                    indFactor3 = qfactor3.front();
                    qfactor3.pop();
                } 
                if(uglyNum == 5*indFactor5) {
                    indFactor5 = qfactor5.front();
                    qfactor5.pop();
                } 
            }
            return(uglyNum);
        }
    };
    

Log in to reply
 

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