Ugly Number II ใน C++

หา Ugly Number ตัวที่ n: จำนวนที่เฉพาะตัวประกอบมีแค่ 2, 3, 5 (1 ถือว่าเป็น ugly number)

ตัวอย่าง: 10th ugly number = 12 (ลำดับ: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12)

ขั้นตอนการแก้ปัญหา (DP 3 Pointers)

1. dp[1] = 1, สร้าง dp[n+1]
2. สาม pointer: i2, i3, i5 เริ่มที่ 1 (ชี้ dp[1])
3. ค่าถัดไป: next2 = dp[i2]*2, next3 = dp[i3]*3, next5 = dp[i5]*5
4. วน i = 2..n:
   • dp[i] = min(next2, next3, next5)
   • ถ้าเท่ากับ next2 → i2++, อัปเดต next2
   • ถ้าเท่ากับ next3 → i3++, อัปเดต next3
   • ถ้าเท่ากับ next5 → i5++, อัปเดต next5
5. คืน dp[n]

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> dp(n + 1);
        dp[1] = 1;
        int i2 = 1, i3 = 1, i5 = 1;
        int next2 = 2, next3 = 3, next5 = 5;
        for (int i = 2; i <= n; i++) {
            dp[i] = min({next2, next3, next5});
            if (dp[i] == next2) { i2++; next2 = dp[i2] * 2; }
            if (dp[i] == next3) { i3++; next3 = dp[i3] * 3; }
            if (dp[i] == next5) { i5++; next5 = dp[i5] * 5; }
        }
        return dp[n];
    }
};

int main() {
    Solution ob;
    cout << ob.nthUglyNumber(10);
}

Input

10

Output

12