ProblemPermalink

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 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

ThoughtsPermalink

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

SolutionPermalink

General Idea

Key Observations:

• The kth ugly number is a 2, 3 or 5 multiple of a previous wth ugly number where w is less than i.
• To find the wth ugly number that will lead to ith 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-1th ugly number

Algorithm:

• To find the wth ugly number that would lead to the kth ugly number, we will keep a three indexes:
  • i: the smallest index such that when ith ugly number multiply by 2, the number is more than i-1th 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

ImplementationPermalink