C++ solution in O(N) time using 3 queues


  • 5
    T

    class Solution {
    public:
    int nthUglyNumber(int n) {

        if(n == 1)
            return 1;
        
        queue <unsigned int> q2;
        queue <unsigned int> q3;
        queue <unsigned int> q5;
        
        int count = 1;
        int next_ugly,nth_ugly;
        
        q2.push(2);
        q3.push(3);
        q5.push(5);
        
        while(count < n)
        {
            next_ugly = std::min(q2.front(),min(q3.front(),q5.front()));
            if(next_ugly == q2.front())
            {
                int val = q2.front();
                q2.push(val*2);
                q3.push(val*3);
                q5.push(val*5);
                q2.pop();
            }
            else if(next_ugly == q3.front())
            {
                int val = q3.front();
                q3.push(val*3);
                q5.push(val*5);
                q3.pop();
            }
            else
            {
                int val = q5.front();
                q5.push(val*5);
                q5.pop();
            }
            count++;
            if(count == n)
                nth_ugly = next_ugly;
        }
        return nth_ugly;
    }
    

    };


  • 0
    L

    I do not understand why it could not come out this situation that given x, y, z, x2 for example is the smallest, but x2 was already in the vector?
    Could you please explain this for me?


  • 0
    T

    The chances are repetition is not possible here....even if I am maintaining 3 queues of multiples of 2, 3 and 5 each. Now observe the code is having if-else-if ladder. It's like every time there is a new minimum...moreover if it's from 2's queue I am pushing data in all queues.But if it's from 3's queue I am only pushing data in 3's & 5's queue (not in 2's queue obeserve 23 32 eliminated) just like that in last only pushing in 5's queue(not in 2's & 3's queue to eliminate situations like 35 53 25 52). Everytime bigger minimum will come and due to more restrictive & selective push each queue will be having bigger & distinct elements.
    But better use a min priority queue of size 3 for this problem. That will be more easy & short.


Log in to reply
 

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