➜ ~

Playing Hacks and Stuffs!

Project maintained by h4ckyou Hosted on GitHub Pages — Theme by mattgraham

Ugly Number II

image

I spent some good amount of time coming up with an overkill solution

But after looking at the discuss forum I saw someone else solution which was way better and the right approach

Here’s it:

Seeing the description we can arrive at the observation that bigger ugly numbers can be generated by multiplying smaller ugly numbers by 2, 3 and 5. In order to be exhaustive, we have to multiply every ugly number by 2, 3, and 5 do make sure we don’t miss any. The problem with that if you run this method on the first few ugly numbers:

1 -> 2, 3, 5 ... 2 -> 4, 6, 10 ... 3 -> 6, 9, 15

The problem with this is that there are going to be duplicates and if you simply append the 3 new ugly numbers at the end of your ugly number array then they will be out of order (unsorted), so it’ll be hard to find the n-th ugly number. The naive way could be adding to a set and then sort the set and get the n-th ugly number but that wouldn’t be efficient (this is the overkill approach script I made)

Therefore the OP’s solution is having 3 pointers, namely i2, i3, and i5, they will keep track of which multiple of 2, 3, 5 of the smaller ugly number they are pointing to. At every loop, you get three multiples of 2, 3 and 5 and you pick the smallest one to append to the ugly number array, this will fix the problem with new ugly number being unsorted, and since we appended that smallest next ugly number, increment the pointer that generated that smallest ugly number so we can add the next bigger one in the future. Since the if-statements are parallel, this also prevent duplicates from being added to the ugly number array, since if two or three u2, u3, and u5 are the same, their corresponding pointer will all be incremented.

Therefore after n-1 loops has executed, we have generated n ugly numbers, and the last number ugly[-1] will indeed be our answer.

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        ugly = [1]
        i2, i3, i5 = 0, 0, 0
        while n > 1:
            u2, u3, u5 = 2 * ugly[i2], 3 * ugly[i3], 5 * ugly[i5]
            umin = min((u2, u3, u5))
            if umin == u2:
                i2 += 1
            if umin == u3:
                i3 += 1
            if umin == u5:
                i5 += 1
            ugly.append(umin)
            n -= 1
        return ugly[-1]

It works pretty well compared to mine image