Question1
An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.
Given an integer n, return true if n is an ugly number**.
Algorithm1
Easy implementation, check if the number can be divided by 2 or 3 or 5, otherwise it's not an ugly number.
Code1
class Solution { public boolean isUgly(int n) { if (n <= 0) return false; while (n % 2 == 0) { n /= 2; } while (n % 3 == 0) { n /= 3; } while (n % 5 == 0) { n /= 5; } return n == 1; } }
Question2
An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.
Given an integer n, return the nth ugly number.
Algorithm2
This question is to generate the ugly number. Start from num1, and each time it pick the smallest number from current number multiple 2 or 3 or 5.
Code2
class Solution { public int nthUglyNumber(int n) { int index2 = 0, index3 = 0, index5 = 0; int[] nums = new int[n]; nums[0] = 1; for (int i = 1; i < n; i++) { int num2 = nums[index2] * 2; int num3 = nums[index3] * 3; int num5 = nums[index5] * 5; nums[i] = Math.min(num2, Math.min(num3, num5)); if (nums[i] == num2) index2++; if (nums[i] == num3) index3++; if (nums[i] == num5) index5++; } return nums[n - 1]; } }