Chương trình tìm số xấu thứ n trong C++

Số xấu (ugly number) là số có các ước số nguyên tố chỉ là 2, 3, 5. Cho số n, tìm số xấu thứ n. Ví dụ 10 số xấu đầu tiên: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12. Số xấu thứ 10 là 12.

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

• Mảng v lưu các số xấu, v[1] = 1.
• 3 con trỏ twoIdx, threeIdx, fiveIdx trỏ đến số xấu sẽ nhân với 2, 3, 5 để tạo số xấu tiếp theo.
• 3 biến two = 2, three = 3, five = 5 là ứng viên tiếp theo.
• Lặp từ 2 đến n: lấy min của 3 ứng viên → số xấu tiếp theo. Cập nhật con trỏ và ứng viên tương ứng.

Ví dụ triển khai

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

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> v(n + 1);
        if (n == 1) return 1;
        int two = 2, three = 3, five = 5;
        int twoIdx = 2, threeIdx = 2, fiveIdx = 2;
        for (int i = 2; i <= n; i++) {
            int curr = min({two, three, five});
            v[i] = curr;
            if (curr == two) {
                two = v[twoIdx] * 2;
                twoIdx++;
            }
            if (curr == three) {
                three = v[threeIdx] * 3;
                threeIdx++;
            }
            if (curr == five) {
                five = v[fiveIdx] * 5;
                fiveIdx++;
            }
        }
        return v[n];
    }
};

int main() {
    Solution ob;
    cout << ob.nthUglyNumber(15);
    return 0;
}

Đầu vào

15

Đầu ra

24