## Similar Problems

Similar Problems not available

# Ugly Number Ii - Leetcode Solution

## Companies:

LeetCode: Ugly Number Ii Leetcode Solution

Difficulty: Medium

Topics: math hash-table dynamic-programming heap-priority-queue

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:

- Initialize the
`ugly`

array with the first ugly number 1. - 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. - 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.

- 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)

## Ugly Number Ii Solution Code

`1`