Số xấu thứ n (Ugly Number II) trong C++

Mô tả bài toán

Số xấu (ugly number) là số chỉ có thừa số nguyên tố 2, 3, 5. Tìm số xấu thứ n (1-indexed).

Ví dụ: n=10 → 12 (dãy: 1,2,3,4,5,6,8,9,10,12).

Giải thuật 3 con trỏ (DP)

1. Mảng ugly size n+1, ugly[1]=1.
2. 3 con trỏ i2, i3, i5 trỏ đến vị trí nhân 2,3,5 tiếp theo.
3. Tại bước k: next = min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5).
4. ugly[k] = next. Tăng con trỏ nào cho giá trị bằng next.

Đảm bảo sinh ra dãy tăng dần, không trùng lặp.

Cài đặt C++

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

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> ugly(n + 1);
        ugly[1] = 1;
        int i2 = 1, i3 = 1, i5 = 1;
        for (int k = 2; k <= n; k++) {
            int n2 = ugly[i2] * 2, n3 = ugly[i3] * 3, n5 = ugly[i5] * 5;
            int next = min({n2, n3, n5});
            ugly[k] = next;
            if (next == n2) i2++;
            if (next == n3) i3++;
            if (next == n5) i5++;
        }
        return ugly[n];
    }
};

int main() {
    Solution ob;
    cout << ob.nthUglyNumber(10); // 12
    return 0;
}

Độ phức tạp

• Thời gian: O(n).
• Không gian: O(n) (có thể O(1) nếu chỉ cần kết quả cuối).