Reference: Problem I & Problem II
Difficulty: Easy

## Problem

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

Ugly numbers are positive numbers whose 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:

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

If not:

Here is the code:

Time: $O(\log{N})$ since the num / 2 can only occur in $\log{N}$ times at most.
Space: $O(\log{N})$

### Iteration

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

## Ugly Number II

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Note:

• 1 is typically treated as an ugly number.
• n does not exceed 1690.

Example:

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

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.

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

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.