# Leetcode 264 - Ugly number II

Note:

• DP

• Given a sequence of nums and find the next num. Is that a classic DP question?
• But how do we know what the next num is?
• All prev nums are got by multiplying 2, 3 or 5. Numbers that are got by 2 are like 1, 2, 4, 6, ....
• Likewise, nums that are got by 3 are like 1, 3, 6, 9, .... So, if you multiply any of prev num with 2, 3, 5, the num you get will be included in the ugly[].
• We need 3 Pointers as indexes tracking which num 2, 3 or 5 should multiply with. Start with dp[0].
• Find the min among dp[p2] * 2, dp[p3] * 3, dp[p5] * 5.
• By comparing min with dp[p2] * 2, dp[p3] * 3, dp[p5] * 5. If true, p++.
• Min Heap

• In case of duplicates, use Set() to check duplicates.

Question:

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:

Code:

MinHeap