Java Easy Understand O(n) Solution
The basic idea of this problem is to compute all the ugly numbers in sequence and count to the given number of k ugly numbers. The way I approached this problem
The basic idea of this problem is to compute all the ugly numbers in sequence and count to the given number of k ugly numbers. The way I approached this problem is first I have a arraylist to store the ugly numbers in sequence. Then I declared three counter variables: a,b,and c which represent the corresponding index in the arraylist for the multiplier of 2,3,and 5. Since each previous ugly number times one of the multiplier will produce a new ugly number, I start from the starting index 0 and multiply the ugly number at that index with each multiplier and get the smallest product which is the next ugly number from the three. The corresponding multipliers' index will be incremented by one and we do this recursively until we have K ugly numbers. Here is the code implementation in Java:\n\n    public class Solution {\n    \tpublic int nthUglyNumber(int n) {\n    \t\tif(n<=0) return 0;\n    \t\tint a=0,b=0,c=0;\n    \t\tList<Integer> table = new ArrayList<Integer>();\n    \t\ttable.add(1);\n    \t\twhile(table.size()<n)\n    \t\t{\n    \t\t\tint next_val = Math.min(table.get(a)*2,Math.min(table.get(b)*3,table.get(c)*5));\n    \t\t\ttable.add(next_val);\n    \t\t\tif(table.get(a)*2==next_val) a++;\n    \t\t\tif(table.get(b)*3==next_val) b++;\n    \t\t\tif(table.get(c)*5==next_val) c++;\n    \t\t}\n    \t\treturn table.get(table.size()-1);\n    \t}\n    }
['Java']