### Find nth Ugly Number uglynumber dynamicprogramming    Posted: 5 years ago Updated: 4 years ago Edit answers (1) views (4519)

Write a function to find the $$n^{th}\ ugly$$ number.

 Posted: 5 years ago Updated: 5 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 thealready 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. Time complexity = $$O(n)$$, space complexity = $$O(n)$$.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]; }