C++, one pass, simple solution.


  • 28
    D

    Use three index for 2, 3, 5 in to trace the last generated numbers based on 2, 3, 5 and generate next number based on the last generated numbers.

    class Solution {
    public:
        int nthUglyNumber(int n) {
            if(n<1)
                return 0;
    
            int id2=0, id3=0, id5=0, rst=1;
            vector<int> buf;
    
            while(--n)
            {
                buf.push_back(rst);
    
                int v2 = 2*(buf[id2]), v3 = 3*(buf[id3]), v5 = 5*(buf[id5]);
                rst = min(v2, min(v3, v5));
                
                id2 += (rst == v2), id3 += (rst == v3), id5 += (rst == v5);
            }
            return rst;
        }
    };

  • 0
    S

    very nice, it took me a moment to realize this indeed works. But wouldn't it have the issue of overflowing beyond the 4 byte int expression limit value?


  • 0
    R

    It could not avoid this problem if you are going to multiply the number.


  • 1
    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?


Log in to reply
 

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