Find the n-th ugly number.

Problem: Write a method to find the nth ugly number.

Example(Taken from leetcode):

Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Approach: Use DP. Maintain a Table where Table[i] tells the (i + 1)th ugly number. Obviously Table[n - 1] will be our answer. Here is how we fill this table:

• Table[0] = 1 
• Maintain three variables; NumOfTwo, NumOfThree and NumOfFive. These variable will tell how many number of 2s, 3s or 5s are involved in the product till now. Initialized to 0.
• FOR i = 0 to n - 1 // first ugly number is already in the table
• NextUglyNumber = Min ( 2 * Table[NumOfTwo], 3 * Table[NumOfThree ], 5 * Table[NumOfFive])
• Add NextUglyNumber to Table
• Increment one of NumOfTwo, NumOfThree and NumOfFive based on which one of them out of 2 * Table[NumOfTwo], 3 * Table[NumOfThree ] and 5 * Table[NumOfFive] is minimum.
• Return Table[n - 1]

Implementation in C#: 

        public static int NthUglyNumber(int n)

        {

            if (n == 0)

            {

                return 0;

            }

            List<int> table = new List<int> { 1 };

            int numOfTwo = 0, numOfThree = 0, numOfFive = 0;

            for (int i = 0; i < n - 1; ++i)

            {

                int nextUglyNumber = Min(2 * table[numOfTwo], 3 * table[numOfThree], 5 * table[numOfFive]);

                if (nextUglyNumber == 2 * table[numOfTwo])

                {

                    ++numOfTwo;

                }

                if (nextUglyNumber == 3 * table[numOfThree])

                {

                    ++numOfThree;

                }

                if (nextUglyNumber == 5 * table[numOfFive])

                {

                    ++numOfFive;

                }

                table.Add(nextUglyNumber);

            }

            return table.Last();

        }

        private static int Min(params int[] values)

        {

            return Enumerable.Min(values);

        }

Complexity: O(n)