How to Solve Ugly Number Problem?

Description

Ugly number is a number that only have prime factors 2, 3 and 5.

Design an algorithm to find the nth ugly number. The first 10 ugly numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

Example

Example 1:
Input: 9
Output: 10

Example 2:
Input: 1
Output: 1

Step by Step Solution

First of all , let’s break down this problem into small problems -

1. Determine if a particular number is ugly number?
2. Then starting from the number 1, keep increasing by 1, check each number to see if it is ugly number, till we find out the nth number.

Sounds like a good plan, right? OK, now let’s translate the English into some pseudocode. Based on the definition of ugly number —

Ugly number is a number that only have prime factors 2, 3 and 5.

It means for a given n, it is like n = 2*x + 3*y + 5*z. (x,y,z is positive integer). So how to check if a particular number is ugly number? What we can do is try to divide the number by 2,3,5, until the mod not equals to 0. In the end, if it is 1, then it should be the ugly number, otherwise not.

We can write some logical block as follows,

This is a good starting point, right? Since we resolve the first small problem. Now let’s do the second part, a loop could resolve our problem. Now we could come up with our first solution.

Looks cool, right? However, the challenge continues.

Please implement the solution with O(n log n) or O(n) time.

Hmm, our first solution is not time efficient since there is too many loops. Think about today’s big data world, what is the strategy of making things faster? The trick is exchange the time with space.

So can we do the same strategy here?

Let’s see if we could reduce a loop by leveraging the space to store some “middle value”. Let’s look at our formula again n = 2*x + 3*y + 5*z and think through if we can find out some pattern, the pattern I will more focus on is how to get the next number from the previous number, why? It is because with the strategy I can leverage the advantage of space to do calculation.

1st ugly number: 1;

2st ugly number: n = 2*1 + 3*0 + 5*0 = 2 => 2* (1st ugly number)

3rd ugly number: n= 2*0 + 3*1 + 5*0 = 3 => 3* (1st ugly number)

4th ugly number: n= 2*2+ 3*0 + 5*0 = 4 => 2 * (2nd ugly number)

5th ugly number: n= 2*0+ 3*0 + 5*1 = 5 => 5 * (1st ugly number)

6th ugly number: n= 2*0+ 3*2+ 5*0 = 6 => 2 * (3rd ugly number) => 3 * (2nd ugly number)

7th ugly number: n= 2*4+ 3*0 + 5*0 = 8=> 2* (4th ugly number)

8th ugly number: n= 2*0+ 3*3 + 5*0 = 9=> 3* (3rd ugly number)

ok now if I use an array to store the nth ugly number, like ugly[n], so I could find out the pattern is that

the ugly[n] must always be 2*ugly[i], 3*ugly[j] or 5*ugly[k] (i,j,k < n and it is always calculated). So to get that particular ugly[n], we just need to try with 2*ugly[i], 3*ugly[j] or 5*ugly[k] and find out the minimum number

ok, let’s translate that into the following js code

ok, let’s see if we solve the challenge.

Accepted, bingo!