Ugly Number II

Medium Topics Company Tags

List the positive integers whose prime factors are all among 2, 3, and 5, in increasing order without duplicates. The value 1 is included because it has no prime factors. Return the nth value in this list, using 1-based indexing.

Example 1:

Input: n = 7

Output: 8

Explanation: The first seven values are 1, 2, 3, 4, 5, 6, and 8. The value 7 is excluded because its prime factor is 7.

Example 2:

Input: n = 12

Output: 16

Explanation: The first twelve values are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, and 16, so the answer is 16.

Example 3:

Input: n = 1

Output: 1

Explanation: The sequence starts with 1, which has no prime factors and is included by definition.

Constraints:

  • 1 <= n <= 1690


Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.