Monday, October 5, 2015

[Leetcode] Ugly Number II, Solution

Write a program to find the `n`-th ugly number.
Ugly numbers are positive numbers whose prime factors only include `2, 3, 5`. For example, `1, 2, 3, 4, 5, 6, 8, 9, 10, 12` is the sequence of the first `10` ugly numbers.
Note that `1` is typically treated as an ugly number.

[Thoughts]

Ugly Number:       1,         2,          3,           4,           5,           6,            8,         10,     ..............

1*3      2*3        3*3         4*3         5*3         6*3         8*3        10*3  .............. *3
1*5      2*5        3*5         4*5         5*5         6*5         8*5        10*5  .............. *5

[Code]
``````1:  class Solution {
2:  public:
3:    int nthUglyNumber(int n) {
4:      vector<int> uglys(1, 1);
5:      int p2 = 0, p3 = 0, p5 = 0;
6:      while (uglys.size() < n) {
7:        int ugly2 = uglys[p2] * 2, ugly3 = uglys[p3] * 3, ugly5 = uglys[p5] * 5;
8:        int min_v = min(ugly2, min(ugly3, ugly5));
9:        if (min_v == ugly2) ++p2;
10:        if (min_v == ugly3) ++p3;
11:        if (min_v == ugly5) ++p5;
12:        if(min_v != uglys.back()) {
13:          // skip duplicate
14:          uglys.push_back(min_v);
15:        }
16:      }
17:      return uglys[n-1];
18:    }
19:  };
``````

``````1:  class Solution {
2:  public:
3:    int nthUglyNumber(int n) {
4:      vector<int> factors{ 2, 3, 5};
5:      return nthUglyNumberGeneral(n, factors);
6:    }
7:    int nthUglyNumberGeneral(int n, vector<int>& factors) {
8:      vector<int> uglys(1,1);
9:      vector<int> indexes(factors.size(), 0);
10:      while(uglys.size() < n) {
11:        int min_v = INT_MAX;
12:        int min_index = 0;
13:        for(int k =0; k< factors.size(); k++) {
14:          int temp = uglys[indexes[k]] * factors[k];
15:          if(temp < min_v) {
16:            min_v = temp;
17:            min_index = k;
18:          }
19:        }
20:        indexes[min_index]++;
21:        // need to avoid duplicate ugly number
22:        if(uglys[uglys.size()-1] != min_v) {
23:          uglys.push_back(min_v);
24:         }
25:      }
26:      return uglys[n-1];
27:    }
28:  };
``````