264. Ugly Number II | Brute Force to Optimization | DP C++

 264. Ugly Number II

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return the nth ugly number.

 

Example 1:

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

Example 2:

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

 

Constraints:

• 1 <= n <= 1690


Solution - 

We will start with brute force and we will make a set to store all ugly numbers in sorted order as it will also be unique.

We will generate all the possible ugly numbers and will insert them into the set.

In the end, we will return the nth number.


To optimize it we can use DP and we will store the ugly numbers in the vector.