## Problem

**Problem ID**: 264

**Title**: Ugly Number II

**Difficulty**: Medium

**Description**:

An **ugly number** is a positive integer whose prime factors are limited to `2`

, `3`

, and `5`

.

Given an integer `n`

, return *the* `n`

^{th}* ugly number*.

**Example 1:**

Input:n = 10Output:12Explanation:[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.

**Example 2:**

Input:n = 1Output:1Explanation:1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.

**Constraints:**

`1 <= n <= 1690`

## Thoughts

I found this problem very hard and had to look at the solution.

## Solution

**General Idea**

Key Observations:

- The
`k`

th ugly number is a`2`

,`3`

or`5`

multiple of a previous`w`

th ugly number where`w`

is less than`i`

. - To find the
`w`

th ugly number that will lead to`i`

th ugly number,`w`

is either the index of a previous ugly number that multiple by`2`

,`3`

or`5`

will give the an ugly number that is just above`i-1`

th ugly number

Algorithm:

- To find the
`w`

th ugly number that would lead to the`k`

th ugly number, we will keep a three indexes:`i`

: the smallest index such that when`i`

th ugly number multiply by`2`

, the number is more than`i-1`

th ugly number`j`

: same as`i`

but for`3`

`k`

: same as`i`

but for`5`

- Advance
`i`

,`j`

,`k`

by`1`

every time we compute a new ugly number

### Implementation