Elegant C++ Solution O(N) space time with detailed explanation.


  • 130
    F
    struct Solution {
        int nthUglyNumber(int n) {
            vector <int> results (1,1);
            int i = 0, j = 0, k = 0;
            while (results.size() < n)
            {
                results.push_back(min(results[i] * 2, min(results[j] * 3, results[k] * 5)));
                if (results.back() == results[i] * 2) ++i;
                if (results.back() == results[j] * 3) ++j;
                if (results.back() == results[k] * 5) ++k;
            }
            return results.back();
        }
    };
    

    Explanation:

    The key is to realize each number can be and have to be generated by a former number multiplied by 2, 3 or 5
    e.g.
    1 2 3 4 5 6 8 9 10 12 15..
    what is next?
    it must be x * 2 or y * 3 or z * 5, where x, y, z is an existing number.

    How do we determine x, y, z then?
    apparently, you can just traverse the sequence generated by far from 1 ... 15, until you find such x, y, z that x * 2, y * 3, z * 5 is just bigger than 15. In this case x=8, y=6, z=4. Then you compare x * 2, y * 3, z * 5 so you know next number will be x * 2 = 8 * 2 = 16.
    k, now you have 1,2,3,4,....,15, 16,

    Then what is next?
    You wanna do the same process again to find the new x, y, z, but you realize, wait, do I have to
    traverse the sequence generated by far again?

    NO! since you know last time, x=8, y=6, z=4 and x=8 was used to generate 16, so this time, you can immediately know the new_x = 9 (the next number after 8 is 9 in the generated sequence), y=6, z=4.
    Then you need to compare new_x * 2, y * 3, z * 5. You know next number is 9 * 2 = 18;

    And you also know, the next x will be 10 since new_x = 9 was used this time.
    But what is next y? apparently, if y=6, 6*3 = 18, which is already generated in this round. So you also need to update next y from 6 to 8.

    Based on the idea above, you can actually generated x,y,z from very beginning, and update x, y, z accordingly. It ends up with a O(n) solution.


  • 0
    B

    your solution is really awesome. could you please explain basic idea behind this and how you came up this solution. thanks


  • 0
    B
    This post is deleted!

  • 0
    F

    I added detailed explanation in my post.


  • 0
    B

    thanks so much


  • 0
    U

    We can improve it by saving the results already figured out and move only as needed , so the time and space complexity will be O(max(query_n)). By bit operations we can also save some time.
    Following solution beats 98.71% of cpp submissions:

    class Solution {
    public:
        int nthUglyNumber(int n) {
            static vector<int> ugly = {0, 1};
            static int p2 = 1, p3 = 1, p5 = 1;
            static int x2 = 2, x3 = 3, x5 = 5;
            
            if(n < ugly.size()) return ugly[n];
            for(int t = n - ugly.size() + 1; t--; ){
                int x = min({x2, x3, x5});
                ugly.push_back(x);
                if(x2 == x) x2 = ugly[++p2] << 1;
                if(x3 == x){
                    ++p3;
                    x3 = ugly[p3] + (ugly[p3] << 1);
                }
                if(x5 == x){
                    ++p5;
                    x5 = ugly[p5] + (ugly[p5] << 2);
                }
            }
            return ugly[n];
        }
    };

  • 0
    F

    I agree the trick to use static vector works well for OJ, just because of the way how it tests the algorithm. But theoretically, it doesn't improve anything of this algorithm.
    And changes like changing a*5 to a + a<<2 are almost ALWAYS unnecessary in C++. I won't spend time explaining why, but you will eventually understand this by yourself (I once didn't believe it either). One simple test you can do is, whenever you feel like you want to make a change like this in the future, compare the run time before and after the change. You won't notice a difference.


  • 0
    A

    great solution man


  • 0

  • 1
    F

    I read the post you provided in the link. So the conclusion is, in best scenario:
    “If you don't care about scalability, you're working with a small program, and you never, ever expect that anyone else besides yourself will be using your program, go ahead and hack up some crazy low-level bit shifts in your C code. Take comfort knowing that you've spent an hour longer in development to save 20 picoseconds per execution.”
    I agree with it. This was my point too. With the time / readability / etc you sacrifice, you will always find a better place to improve, because an improvement like changing *2 to >>1 is almost never the bottleneck of your system.


  • 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
    F

    Up for the explanation.

    It's better to check the range to avoid overflow,

    if(n <= 0 || n > 1691) return 0;
    

    For a more robust and general solution, it's better to check the overflow before min() function. It's possible that a[i] * p overflows while a[j] * q remains valid.

    For fun: there are total 1691 ugly numbers in range int32, so there is an O(1) solution available. :)
    but oj fails to compute the last one :(

    # no.1690
    2125764000: 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 5 5 5
    # no.1691
    2123366400: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 5 5

  • 0
    H

    In your example, I found a trivial error, the penultimate paragraph. Since 6*3=18 and 18 already existed in result, we need to update next y from 6 to 7,not 8.


Log in to reply
 

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