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.
To optimize it we can use DP and we will store the ugly numbers in the vector.
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.