264. 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. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number, and n does not exceed 1690.

Solution:

Bottom-up dp.

All the ugly numbers should be product of an ugly number and 2 or 3 or 5. 

We use an array to track all the ugly numbers we calculated so far and use three pointers to track which ugly number is the next ugly number that we are going to use to build nth ugly number for 2,3,and 5 respectively. 

For example when we get ugly number 10, which is 2 * 5, the next ugly number for factor 2 that is possible to build an ugly number next to 10 is 6, and next ugly number that for factor 3 is 4 since 9 is build by 3 * 3, so next is 4 for factor 3. The next ugly number for factor five becomes 3, because 10 is 2*5, so the pointer moves to 3. We compare all 3 candidates, 2*6, 3*4, 5*3 and get the minimum which is 12, and increment the pointers respectively.

 public int nthUglyNumber(int n) {  
     int[] res=new int[n];  
     res[0]=1;  
     int a,b,c;  
     a=b=c=0;  
     for(int i=1;i<n;i++){  
       res[i]=Math.min(2*res[a],Math.min(3*res[b],5*res[c]));  
       if(res[i]%2==0) a++;  
       if(res[i]%3==0) b++;  
       if(res[i]%5==0) c++;  
     }  
     return res[n-1];  
   }