Leetcode 264. Ugly Number II

Problem Explanation:

Given an integer (n), we need to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3 and 5. It is typically agreed upon that 1 is considered as an ugly number.

For instance, if n equals 10, the sequence of the first 10 ugly numbers is 1, 2, 3, 4, 5, 6, 8, 9, 10, 12. So the output of the function would be 12.

Solution Approach:

The solution to this problem uses the concept of dynamic programming. A dynamic array (named uglyNums in the solution) is used to store the calculated ugly numbers in increasing order. The initial elements of uglyNums are always 1 (since 1 is considered an ugly number).

Three counters (i2, i3 and i5) correspond to factors 2, 3 and 5. Each time we generate a new ugly number, it could be the previous ugly number multiply by either 2, 3 or 5. So each step, we calculate potential next ugly numbers as "next2", "next3" and "next5", and then choose the smallest one to be the next ugly number.

The chosen number’s corresponding factor's count is incremented for the next move. This process continues until we fill the entire array.

C++ Solution:

1
2cpp
3class Solution {
4 public:
5  int nthUglyNumber(int n) {
6    vector<int> uglyNums{1};
7    int i2 = 0;
8    int i3 = 0;
9    int i5 = 0;
10
11    while (uglyNums.size() < n) {
12      // Calculate potential next ugly numbers
13      const int next2 = uglyNums[i2] * 2;
14      const int next3 = uglyNums[i3] * 3;
15      const int next5 = uglyNums[i5] * 5;
16      
17      // Find minimum
18      const int next = min({next2, next3, next5});
19
20      // Increment the count of the factor which will use for the next minimum ugly number
21      if (next == next2) ++i2;
22      if (next == next3) ++i3;
23      if (next == next5) ++i5;
24
25      // Push the new ugly number to the array
26      uglyNums.push_back(next);
27    }
28    
29    // Return the nth ugly number
30    return uglyNums.back();
31  }
32};

Note: Solutions for python, java, javascript, and c# are not included here. They are to be drafted separately with similar logic mentioned above. Algorithm, implementation steps and the working of algorithm remain same as above.# Python Solution:

1
2python
3def nthUglyNumber(n):
4    uglyNums = [1]
5    index2, index3, index5 = 0, 0, 0
6
7    while len(uglyNums) < n:
8        next2, next3, next5 = uglyNums[index2]*2, uglyNums[index3]*3, uglyNums[index5]*5
9        nextUgly = min(next2, next3, next5)
10        if nextUgly == next2:
11            index2 += 1
12        if nextUgly == next3:
13            index3 += 1
14        if nextUgly == next5:
15            index5 += 1
16      
17        uglyNums.append(nextUgly)
18
19    return uglyNums[-1]

JavaScript Solution:

1
2javascript
3function nthUglyNumber(n) {
4    let uglyNums = [1];
5    let index2 = 0, index3 = 0, index5 = 0;
6
7    while (uglyNums.length < n) {
8      let next2 = uglyNums[index2]*2;
9      let next3 = uglyNums[index3]*3;
10      let next5 = uglyNums[index5]*5;
11
12      let nextUgly = Math.min(next2, next3, next5);
13
14      if (nextUgly === next2) 
15          index2++; 
16      if (nextUgly === next3) 
17          index3++; 
18      if (nextUgly === next5) 
19          index5++; 
20
21      uglyNums.push(nextUgly);
22    }
23
24    return uglyNums[n-1];
25}

Java Solution:

1
2java
3public int nthUglyNumber(int n) {
4     int uglyNums[] = new int[n];
5     uglyNums[0] = 1;
6     int index2 = 0, index3 = 0, index5 = 0;
7     int next2 = 2, next3 = 3, next5 = 5;
8
9     for(int i = 1; i < n; i++) {
10         int nextUgly = Math.min(next2, Math.min(next3, next5));
11         uglyNums[i] = nextUgly;
12
13         if (nextUgly == next2) 
14             next2 = uglyNums[++index2] * 2; 
15         if (nextUgly == next3)
16             next3 = uglyNums[++index3] * 3;
17         if (nextUgly == next5)
18             next5 = uglyNums[++index5] * 5;
19     }
20
21     return uglyNums[n - 1];
22}

In these solutions, while loop continues until we reach the nth ugly number. To generate the next ugly number, we choose the minimum between next2, next3, and next5, and increment the corresponding index of the selected number. Then append this minimum value to the uglyNums list or array. Finally, return the last element of uglyNums as the nth ugly number.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫