Reference: Problem I & Problem II

Difficulty: Easy

My Post: Summary of Ugly Number I & II (dp, priority-queue)

## Problem

Write a program to check whether a given number is an ugly number.

Ugly numbers are

positive numberswhose`prime factors`

only include`2, 3, 5`

.

**Note:**

`Non-prime factors`

are allowed, e.g.`8`

is an ugly number.`1`

is typically treated as an ugly number.- Input is within the 32-bit signed integer range: $[−2^{31}, 2^{31} − 1]$.

**Example:**

1 | Input: -1, 0 |

## Analysis

The brute-force solution is to check all prime factors of `num`

. By examining prime factors, determining if the factor is a prime is costly.

### Recursion

The idea is that if a number `num`

has factors `2, 3, 5`

remove the effect of these factors by division. For example, `21`

has a factor `3`

, so we can determine if it is an ugly number by indirectly checking if `21 / 3`

is an ugly number.

If `num`

is an ugly number, we will be at last examining `num = 1`

.

1 | 30 / 2 = 15 |

If not:

1 | 31 --> false (cannot be divided by 2, 3, 5) |

Here is the code:

1 | public boolean isUgly(int num) { |

**Time:** $O(\log{N})$ since the `num / 2`

can only occur in $\log{N}$ times at most.**Space:** $O(\log{N})$

### Iteration

1 | public static boolean isUgly(int num) { |

**Time:** $O(\log{N})$**Space:** $O(1)$

## Ugly Number II

Write a program to find the

`n-th`

ugly number.

Ugly numbers are

positive numberswhose`prime factors`

only include`2, 3, 5`

.

**Note:**

`1`

is typically treated as an ugly number.`n`

does not exceed 1690.

**Example:**

1 | Input: n = 10 |

### Brute-force

1 | int[] divisors = new int[] { 2, 3, 5 }; |

### Priority Queue

An ugly number must be multiplied by either `2, 3, 5`

from a smaller ugly number. We can use a priority queue, but have to remove duplicates when polling elements from it.

**Note:**

- Use
`long`

since we may put in very large elements in advance, say`val * 5`

, although they are not within the range of`n`

. `(int) Long`

,`(Integer) Long`

are illegal.

1 | public int nthUglyNumber(int n) { |

**Time:** $O(N\log{N})$**Space:** $O(N)$

### DP (clever)

Since `1 <= n <= 1690`

, we can pre-compute `n`

ugly numbers and return the result in constant time.

1 | int BOUND = 1690; |

**Time:** $O(N)$**Space:** $O(N)$