leetcode

0 // Brute force solution

1 class Solution {

2 public:

3 int nthUglyNumber(int n) {

4 priority_queue<long long, vector<long long>, greater<long long>> pq;

5 unordered_set<long long> us;

6 int count;

7

8 pq.push(1);

9 count = 1;

10 while (!pq.empty() && count < n) {

11 long long n = pq.top();

12 pq.pop();

13 for (int i : {2, 3, 5}) {

14 if (us.count(n * i)) continue;

15 pq.push(n * i);

16 us.insert(n * i);

17 }

18 count++;

19 }

20

21 return (int)pq.top();

22 }

23 };

24

25 // DP solution

26 class Solution {

27 public:

28 int nthUglyNumber(int n) {

29 vector<int> k(n);

30 k[0] = 1;

31 int t2 = 0, t3 = 0, t5 = 0;

32 for (int i = 1; i < n; i++) {

33 k[i] = min(k[t2] * 2, min(k[t3] * 3, k[t5] * 5));

34 t2 += k[i] == k[t2] * 2;

35 t3 += k[i] == k[t3] * 3;

36 t5 += k[i] == k[t5] * 5;

37 }

38 return k.back();

39 }

40 };