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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Input: -1, 0
Output: false

Input: 1
Output: true

Input: 2, 3, 5
Output: true
Explanation: although they are primes, they are ugly.

Input: 7, 11
Output: false
Explanation: They are primes, but they are not ugly. They are other prime factors themselves.

Input: 4
Output: true
Explanation: 4 = 1 x 4, 2 x 2 (no other prime factors)

Input: 6
Output: true
Explanation: 6 = 1 x 6, 2 × 3 (no other prime factors)

Input: 21
Output: false
Explanation: 21 = 3 x 7 (7 is the other prime factor)

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
2
3
30 / 2 = 15
15 / 3 = 5
 5 / 5 = 1 --> true

If not:

1
2
31         --> false (cannot be divided by 2, 3, 5)
21 / 3 = 7 --> false (cannot be divided by 2, 3, 5)

Here is the code:

1
2
3
4
5
6
7
8
public boolean isUgly(int num) {
  if (num <= 0) return false;
  if (num == 1) return true;
  if (num % 2 == 0) return isUgly(num / 2);
  if (num % 3 == 0) return isUgly(num / 3);
  if (num % 5 == 0) return isUgly(num / 5);
  return false;
}

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

Iteration

1
2
3
4
5
6
7
8
public static boolean isUgly(int num) {
  if (num <= 0) return false;
  int[] divisors = { 2, 3, 5 };
  for(int d : divisors) {
    while (num % d == 0) num /= d;
  }
  return num == 1;
}

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:

1
2
3
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.

Brute-force

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int[] divisors = new int[] { 2, 3, 5 };
private boolean isUgly(int num) {
  if (num <= 0) return false;
  if (num == 1) return true;
  for (int d : divisors) {
    while (num % d == 0) {
      num /= d;
    }
  }
  return num == 1;
}

public int nthUglyNumber(int n) {
  int num = 1;
  while (n > 0) {
    if (isUgly(num)) {
      --n;
    }
    if (n == 0) break;
    ++num;
  }
  return num;
}

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
2
3
4
5
6
7
8
9
10
11
12
13
public int nthUglyNumber(int n) {
  PriorityQueue<Long> pq = new PriorityQueue<>();
  pq.add(1l);
  for (int i = 0; i < n - 1; ++i) {
    long val = pq.remove();
    while (pq.size() > 0 && pq.peek() == val) pq.remove(); // remove duplicates
    pq.add(val * 2);
    pq.add(val * 3);
    pq.add(val * 5);
  }
  // return (int) pq.remove();   // 
  return pq.remove().intValue();
}

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int BOUND = 1690;
public int nthUglyNumber(int n) {
  // dp[i] denote the i + 1 ugly numbers
  int[] dp = new int[BOUND];
  dp[0] = 1;
  // the smallest number that is not multiplied by 2, 3, 5
  int i2 = 0, i3 = 0, i5 = 0;
  for (int i = 1; i < BOUND; ++i) {
    dp[i] = Math.min(dp[i2] * 2, Math.min(dp[i3] * 3, dp[i5] * 5));
    if (dp[i] == dp[i2] * 2) ++i2;
    if (dp[i] == dp[i3] * 3) ++i3;
    if (dp[i] == dp[i5] * 5) ++i5;
  }
  return dp[n - 1];
}

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