• Posted: 7 years ago
• Updated: 7 years ago
• 0 0
• Edit

Ugly numbers are numbers whose only prime factors are \( 2 \), \( 3 \) or \( 5 \). We use dynamic programming to find the \( n^{th} \) ugly number.

• Declare an array for ugly numbers.
  
• Initialize the first ugly number to be \( 1 \) and \( 3 \) array index variables to point to the first element of the ugly number array.
  
• Fill up the ugly number array : The next ugly number will be the multiplication of the existing ugly numbers with \( 2 \), \( 3 \) or \( 5 \). The existing ugly numbers are multiplied by \( 2 \), \( 3 \) and \( 5 \). In each cases choose the product of the multiplication that is the next greater integer number of the
  already found biggest ugly number. The next ugly number will be the minimum of these three numbers.
  
• Repeat the above until the desired indexed ugly number is found.
  

public int findNthUglyNumber(int n){
     if (n  < = 0)
        return 0;

     int[] uglyNumber = new int[n];
     uglyNumber[0] = 1;
     int nextUglyIndex = 1;
     int index2 = 0;
     int index3 = 0;
     int index5 = 0;

     while (nextUglyIndex  <  n){
        int minimum = Math.min(uglyNumber[index2] * 2, uglyNumber[index3] * 3,
                           uglyNumber[index5] * 5);
        
        uglyNumber[nexUglytIndex] = minimum;

        while (uglyNumber[index2] * 2  < = uglyNumber[nextuglyIndex])
            ++index2;
        while (uglyNumber[index3] * 3  < = uglyNumber[nextUglyIndex])
            ++index3;
        while (uglyNumber[index5] * 5  < = uglyNumber[nextUglyIndex])
            ++index5;

        ++nextUglyIndex;
     }
     return uglyNumber[nextUglyIndex - 1];
 }