//
// Created by 罗炳国 on 2024/1/2.
//

#ifndef PFJ_CODE040_NTHUGLYNUMBER_H
#define PFJ_CODE040_NTHUGLYNUMBER_H

#include "commonHeader.h"

/**
 * 给你一个整数 n ，请你找出并返回第 n 个 丑数 。
 * 丑数 就是质因子只包含 2、3 和 5 的正整数。
 * 264:https://leetcode.cn/problems/ugly-number-ii/description/
 * */

class code040_nthUglyNumber {
public:
    int nthUglyNumber(int n) {
        vector<int> dp(n, 0);
        dp[0] = 1;
        int a = 0, b = 0, c = 0, cur = dp[0];
        for (int i = 1; i < n; i++) {
            cur = min({dp[a] * 2, dp[b] * 3, dp[c] * 5});
            dp[i] = cur;
            if (cur == dp[a] * 2)
                a++;
            if (cur == dp[b] * 3)
                b++;
            if (cur == dp[c] * 5)
                c++;
        }
        return dp[n - 1];
    }

    void test() {
        int a = 1;
        int ans = nthUglyNumber(a);
        std::cout << a << ":" << ans << endl;

        a = 10;
        ans = nthUglyNumber(a);
        std::cout << a << ":" << ans << endl;
    }

};

#endif//PFJ_CODE040_NTHUGLYNUMBER_H