@@ -0,0 +1,1685 @@
+/**%0A * Write a program to find the n-th ugly number.%0A *%0A * Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10,%0A * 12 is the sequence of the first 10 ugly numbers.%0A *%0A * Note that 1 is typically treated as an ugly number.%0A *%0A * Hint:%0A *%0A * The naive approach is to call isUgly for every number until you reach the nth one. Most numbers are not ugly. Try to%0A * focus your effort on generating only the ugly ones.%0A *%0A * An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.%0A *%0A * The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists:%0A * L1, L2, and L3.%0A *%0A * Assume you have Uk, the kth ugly number. Then Uk+1 must be Min(L1 * 2, L2 * 3, L3 * 5).%0A *%0A * Tags: Dynamic Programming, Heap, Math%0A *%0A * Similar Problems: (H) Merge k Sorted Lists, (E) Count Primes, (E) Ugly Number, (M) Perfect Squares, (M) Super Ugly%0A * Number%0A */%0Apublic class UglyNumber2 %7B%0A%0A    public int nthUglyNumber(int n) %7B%0A        if (n %3C= 0) return -1;%0A        if (n == 1) return 1;%0A%0A        // pointers for 2, 3, 5%0A        int p2 = 0;%0A        int p3 = 0;%0A        int p5 = 0;%0A%0A        // generate ugly numbers array%0A        int%5B%5D uglyNums = new int%5Bn%5D;%0A        uglyNums%5B0%5D = 1;%0A        for (int i = 1; i %3C n; i++) %7B%0A            uglyNums%5Bi%5D = Math.min(uglyNums%5Bp2%5D * 2, Math.min(uglyNums%5Bp3%5D * 3, uglyNums%5Bp5%5D * 5));%0A            // update indices%0A            if (uglyNums%5Bi%5D == uglyNums%5Bp2%5D * 2) p2++;%0A            if (uglyNums%5Bi%5D == uglyNums%5Bp3%5D * 3) p3++;%0A            if (uglyNums%5Bi%5D == uglyNums%5Bp5%5D * 5) p5++;%0A        %7D%0A        return uglyNums%5Bn - 1%5D;%0A    %7D%0A%7D%0A

add 264 Ugly Number 2