Summary of Ugly Number I & II (dp, priority-queue)
Reference: Problem I & Problem II\nDifficulty: Easy\n\n## Problem\n\n> Write a program to check whether a given number is an ugly number.\n\n> Ugly numbers are 
Reference: [Problem I](https://leetcode.com/problems/ugly-number/) & [Problem II](https://leetcode.com/problems/ugly-number-ii/)\nDifficulty: <span class="green">Easy</span>\n\n## Problem\n\n> Write a program to check whether a given number is an ugly number.\n\n> Ugly numbers are **positive numbers** whose `prime factors` only include `2, 3, 5`.\n\n**Note:** \n\n- `Non-prime factors` are allowed, e.g. `8` is an ugly number.\n- `1` is typically treated as an ugly number.\n- Input is within the 32-bit signed integer range: `[\u22122^{31},  2^{31} \u2212 1]`.\n\n\n**Example:** \n\n```java\nInput: -1, 0\nOutput: false\n\nInput: 1\nOutput: true\n\nInput: 2, 3, 5\nOutput: true\nExplanation: although they are primes, they are ugly.\n\nInput: 7, 11\nOutput: false\nExplanation: They are primes, but they are not ugly. They are other prime factors themselves.\n\nInput: 4\nOutput: true\nExplanation: 4 = 1 x 4, 2 x 2 (no other prime factors)\n\nInput: 6\nOutput: true\nExplanation: 6 = 1 x 6, 2 \xD7 3 (no other prime factors)\n\nInput: 21\nOutput: false\nExplanation: 21 = 3 x 7 (7 is the other prime factor)\n```\n\n\n## Analysis\n\nThe brute-force solution is to check all prime factors of `num`. By examining prime factors, determining if the factor is a prime is costly.\n\n### Recursion\n\nThe 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.\n\nIf `num` is an ugly number, we will be at last examining `num = 1`.\n\n```java\n30 / 2 = 15\n15 / 3 = 5\n 5 / 5 = 1 --> true\n```\n\nIf not:\n\n```java\n31         --> false (cannot be divided by 2, 3, 5)\n21 / 3 = 7 --> false (cannot be divided by 2, 3, 5)\n```\n\nHere is the code:\n\n```java\npublic boolean isUgly(int num) {\n  if (num <= 0) return false;\n  if (num == 1) return true;\n  if (num % 2 == 0) return isUgly(num / 2);\n  if (num % 3 == 0) return isUgly(num / 3);\n  if (num % 5 == 0) return isUgly(num / 5);\n  return false;\n}\n```\n\n**Time:** `O(logN)` since the `num / 2` can only occur in `logN` times at most.\n**Space:** `O(logN)`\n\n\n\n### Iteration\n\n```java\npublic static boolean isUgly(int num) {\n  if (num <= 0) return false;\n  int[] divisors = { 2, 3, 5 };\n  for(int d : divisors) {\n    while (num % d == 0) num /= d;\n  }\n  return num == 1;\n}\n```\n\n**Time:** `O(logN)`\n**Space:** `O(1)`\n\n\n## Ugly Number II\n\n> Write a program to find the `n-th` ugly number.\n\n> Ugly numbers are **positive numbers** whose `prime factors` only include `2, 3, 5`.\n\n**Note:**\n\n- `1` is typically treated as an ugly number.\n- `n` does not exceed 1690.\n\n**Example:**\n\n```java\nInput: n = 10\nOutput: 12\nExplanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.\n```\n\n### Brute-force\n\n```java\nint[] divisors = new int[] { 2, 3, 5 };\nprivate boolean isUgly(int num) {\n  if (num <= 0) return false;\n  if (num == 1) return true;\n  for (int d : divisors) {\n    while (num % d == 0) {\n      num /= d;\n    }\n  }\n  return num == 1;\n}\n\npublic int nthUglyNumber(int n) {\n  int num = 1;\n  while (n > 0) {\n    if (isUgly(num)) {\n      --n;\n    }\n    if (n == 0) break;\n    ++num;\n  }\n  return num;\n}\n```\n\n### Priority Queue\n\nAn 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.\n\n**Note:** \n\n- Use `long` since we may put in very large elements in advance, say `val * 5`, although they are not within the range of `n`.\n- `(int) Long`, `(Integer) Long` are illegal.\n\n```java\npublic int nthUglyNumber(int n) {\n  PriorityQueue<Long> pq = new PriorityQueue<>();\n  pq.add(1l);\n  for (int i = 0; i < n - 1; ++i) {\n    long val = pq.remove();\n    while (pq.size() > 0 && pq.peek() == val) pq.remove(); // remove duplicates\n    pq.add(val * 2);\n    pq.add(val * 3);\n    pq.add(val * 5);\n  }\n  // return (int) pq.remove();   // \n  return pq.remove().intValue();\n}\n```\n\n**Time:** `O(NlogN)`\n**Space:** `O(N)`\n\n\n\n### DP (clever)\n\nSince `1 <= n <= 1690`, we can pre-compute `n` ugly numbers and return the result in constant time.\n\n```java\nint BOUND = 1690;\npublic int nthUglyNumber(int n) {\n  // dp[i] denote the i + 1 ugly numbers\n  int[] dp = new int[BOUND];\n  dp[0] = 1;\n  // the smallest number that is not multiplied by 2, 3, 5\n  int i2 = 0, i3 = 0, i5 = 0;\n  for (int i = 1; i < BOUND; ++i) {\n    dp[i] = Math.min(dp[i2] * 2, Math.min(dp[i3] * 3, dp[i5] * 5));\n    if (dp[i] == dp[i2] * 2) ++i2;\n    if (dp[i] == dp[i3] * 3) ++i3;\n    if (dp[i] == dp[i5] * 5) ++i5;\n  }\n  return dp[n - 1];\n}\n```\n\n**Time:** `O(N)`\n**Space:** `O(N)`
['Dynamic Programming', 'Heap (Priority Queue)', 'Java']