Ugly Number Ii - Leetcode Solution

Ugly Number II is a problem on Leetcode that requires us to find the nth ugly number. An ugly number is a number that only has 2, 3, or 5 as its prime factors.

Let's start by defining a function nthUglyNumber(n) that takes in an integer n as its parameter and returns the nth ugly number. We will be using dynamic programming to solve this problem.

To solve this problem, we will be using three variables i2, i3, i5 to represent the index of the next ugly number that will be multiplied with 2, 3 and 5 respectively. We will also be using an array ugly to store the sequence of ugly numbers generated so far.

Here's the algorithm:

1. Initialize the ugly array with the first ugly number 1.
2. Initialize i2, i3, and i5 to 0. These variables represent the index in the ugly array that will be multiplied with 2, 3 and 5 respectively.
3. For each ith number in the ugly array:
   • Compute the next possible ugly numbers by multiplying the current ugly numbers with 2, 3, and 5 respectively, that haven't been added to the sequence yet.
   • Find the minimum value among the three possible numbers.
   • Add the minimum value to the ugly array.
   • Update i2, i3, and i5 based on which number was chosen.
4. Return the last element of the ugly array, which represents the nth ugly number.

Here's the code:

def nthUglyNumber(n):
    ugly = [1]
    i2, i3, i5 = 0, 0, 0
    
    while len(ugly) < n:
        # Compute the next possible ugly numbers
        next2 = ugly[i2] * 2
        next3 = ugly[i3] * 3
        next5 = ugly[i5] * 5
        
        # Find the minimum value among the three possible numbers
        next_ugly = min(next2, next3, next5)
        
        # Add the minimum value to the ugly array
        ugly.append(next_ugly)
        
        # Update i2, i3, and i5 based on which number was chosen
        if next_ugly == next2:
            i2 += 1
        if next_ugly == next3:
            i3 += 1
        if next_ugly == next5:
            i5 += 1
            
    return ugly[-1]

Time Complexity: O(n)

Space Complexity: O(n)

1