Ugly Numbers | GeeksforGeeks

Related:
LeetCode 313 - Super Ugly Number
LeetCode 263 + 264 Ugly Number I II
Ugly Numbers | GeeksforGeeks
Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
shows the first 11 ugly numbers. By convention, 1 is included.
Write a program to find and print the 150′th ugly number.

1 Declare an array for ugly numbers:  ugly[150]
2 Initialize first ugly no:  ugly[0] = 1
3 Initialize three array index variables i2, i3, i5 to point to 
   1st element of the ugly array: 
        i2 = i3 = i5 =0; 
4 Initialize 3 choices for the next ugly no:
         next_mulitple_of_2 = ugly[i2]*2;
         next_mulitple_of_3 = ugly[i3]*3
         next_mulitple_of_5 = ugly[i5]*5;
5 Now go in a loop to fill all ugly numbers till 150:
For (i = 1; i < 150; i++ ) 
{
    /* These small steps are not optimized for good 
      readability. Will optimize them in C program */
    next_ugly_no  = Min(next_mulitple_of_2,
                                  next_mulitple_of_3,
                                  next_mulitple_of_5); 
    if  (next_ugly_no  == next_mulitple_of_2) 
    {             
        i2 = i2 + 1;        
        next_mulitple_of_2 = ugly[i2]*2;
    } 
    if  (next_ugly_no  == next_mulitple_of_3) 
    {             
        i3 = i3 + 1;        
        next_mulitple_of_3 = ugly[i3]*3;
     }            
     if  (next_ugly_no  == next_mulitple_of_5)
     {    
        i5 = i5 + 1;        
        next_mulitple_of_5 = ugly[i5]*5;
     } 
     ugly[i] =  next_ugly_no       
}/* end of for loop */ 
6.return next_ugly_no

Java Code:
DP - O(n)
https://github.com/anakiou/JavaAlgorithms/blob/master/src/main/java/com/anakiou/ja/other/dynamic/UglyNumbers.java

	int ugly(int n){ int arr[] = new int[n];
	int count = 1;
	arr[0] = 1;
	int i2 = 0;
	int i3 = 0;
	int i5 = 0;
	while(count < n){
	int minNumber = min(arr[i2]*2, arr[i3]*3,arr[i5]*5);
	if(minNumber == arr[i2]*2){
	i2++;
	}
	if(minNumber == arr[i3]*3){
	i3++;
	}
	if(minNumber == arr[i5]*5){
	i5++;
	}
	arr[count++] = minNumber;
	}
	return arr[n-1];
	}

unsigned getNthUglyNo(unsigned n)

{

    unsigned *ugly =

             (unsigned *)(malloc (sizeof(unsigned)*n));

    unsigned i2 = 0, i3 = 0, i5 = 0;

    unsigned i;

    unsigned next_multiple_of_2 = 2;

    unsigned next_multiple_of_3 = 3;

    unsigned next_multiple_of_5 = 5;

    unsigned next_ugly_no = 1;

    *(ugly+0) = 1;

    for(i=1; i<n; i++)

    {

       next_ugly_no = min(next_multiple_of_2,

                           next_multiple_of_3,

                           next_multiple_of_5);

       *(ugly+i) = next_ugly_no;                   

       if(next_ugly_no == next_multiple_of_2)

       {

           i2 = i2+1;      

           next_multiple_of_2 = *(ugly+i2)*2;

       }

       if(next_ugly_no == next_multiple_of_3)

       {

           i3 = i3+1;

           next_multiple_of_3 = *(ugly+i3)*3;

       }

       if(next_ugly_no == next_multiple_of_5)

       {

           i5 = i5+1;

           next_multiple_of_5 = *(ugly+i5)*5;

       }

    } /*End of for loop (i=1; i<n; i++) */

    return next_ugly_no;

}

http://rosettacode.org/wiki/Hamming_numbers#Java

    private static BigInteger THREE = BigInteger.valueOf(3);
    private static BigInteger FIVE = BigInteger.valueOf(5);
 
    private static void updateFrontier(BigInteger x,
                                       PriorityQueue<BigInteger> pq) {
        pq.offer(x.shiftLeft(1));
        pq.offer(x.multiply(THREE));
        pq.offer(x.multiply(FIVE));
    }
 
    public static BigInteger hamming(int n) {
        if (n <= 0)
            throw new IllegalArgumentException("Invalid parameter");
        PriorityQueue<BigInteger> frontier = new PriorityQueue<BigInteger>();
        updateFrontier(BigInteger.ONE, frontier);
        BigInteger lowest = BigInteger.ONE;
        for (int i = 1; i < n; i++) {
            lowest = frontier.poll();
            while (frontier.peek().equals(lowest))
                frontier.poll();
            updateFrontier(lowest, frontier);
        }
        return lowest;
    }

http://www.algoqueue.com/algoqueue/default/view/9175040/find-nth-ugly-number-

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];

}

int getNthUglyNo(int n)

{

  int i = 1;

  int count = 1;   /* ugly number count */

  /*Check for all integers untill ugly count

    becomes n*/

  while (n > count)

  {

    i++;     

    if (isUgly(i))

      count++;

  }

  return i;

}

aaFind the kth number with only prime factors of 3, 5 and 7
https://sites.google.com/site/csharpofjameschen/home/math/find-the-kth-number-such-that-the-only-prime-factors-are-3-5-and-7

        static int KthFactorOf357(int k)

        {

            int count3 = 0;

            int count5 = 0;

            int count7 = 0;

            List<int> list = new List<int>();

            list.Add(1);

            while (list.Count <= k + 1)

            {

                int m = Math.Min(Math.Min(list[count3] * 3, list[count5] * 5), list[count7] * 7);

                list.Add(m);

                if (m == list[count3] * 3) count3++;

                if (m == list[count5] * 5) count5++;

                if (m == list[count7] * 7) count7++;

            }

            return list[k];

        }

Read full article from Ugly Numbers | GeeksforGeeks