Hiểu bài toán

Xác định xem một số nguyên dương N có phải là 'số gần may mắn' hay không. Theo đề bài, một số được coi là 'gần may mắn' nếu:

1. Đếm số lượng chữ số 5 và 9 trong N, gọi kết quả là C.
2. Nếu C là một số may mắn (chỉ chứa các chữ số 5 và 9), thì N là số gần may mắn. Ví dụ: N = 595. Có 3 chữ số 5 và 9 (tất cả đều là 5 hoặc 9). C = 3. Số 3 không chứa chữ số 5 hay 9 => N không gần may mắn.

Các cách tiếp cận

Cách Xử lý chuỗi trực tiếp

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

bool isLucky(long long x) {
    if (x == 0) return false;
    while (x > 0) {
        int d = x % 10;
        if (d != 5 && d != 9) return false;
        x /= 10;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string N;
    cin >> N;

    long long cnt = 0;
    for (char c : N) {
        if (c == '5' || c == '9') cnt++;
    }

    if (isLucky(cnt)) cout << "YES";
    else cout << "NO";

    return 0;
}

• Time Complexity: O(L) với L là độ dài chuỗi số N
• Space Complexity: O(L)

Đây là cách tiếp cận trực quan nhất và cũng là tối ưu nhất cho bài toán này. Vì N có thể rất lớn (đến 10^1000), ta không thể lưu trữ N dưới dạng số nguyên (long long). Thay vào đó, ta đọc N vào dưới dạng chuỗi ký tự.

1. Duyệt qua từng ký tự của chuỗi N.
2. Nếu ký tự là '5' hoặc '9', tăng biến đếm cnt lên 1.
3. Sau khi đếm xong, cnt là một số nhỏ (tối đa bằng số chữ số của N, ví dụ 1000).
4. Kiểm tra xem cnt có phải là số may mắn (chỉ chứa 5 và 9) bằng hàm isLucky.
5. In kết quả "YES" hoặc "NO".

Cách Xử lý số nguyên (Không khả thi với số lớn)

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

bool isLucky(int x) {
    if (x == 0) return false;
    while (x > 0) {
        int d = x % 10;
        if (d != 5 && d != 9) return false;
        x /= 10;
    }
    return true;
}

int main() {
    long long n;
    cin >> n;

    int cnt = 0;
    long long tmp = n;
    while (tmp > 0) {
        int d = tmp % 10;
        if (d == 5 || d == 9) cnt++;
        tmp /= 10;
    }

    if (isLucky(cnt)) cout << "YES";
    else cout << "NO";

    return 0;
}

• Time Complexity: O(log N)
• Space Complexity: O(1)

Phương pháp này giả định N là một số nguyên dạng long long. Nó chia nhỏ N cho 10 để lấy từng chữ số và đếm. Lưu ý: Solutions được cung cấp có đoạn code này, nhưng nó chỉ hoạt động đúng nếu N đủ nhỏ để chứa trong kiểu long long. Trong các kỳ thi lập trình cạnh tranh, các bài toán dạng này thường có input lớn hơn 2^63. Do đó, cách tiếp cận này có rủi ro tràn số (overflow) nếu input lớn, nên cách tiếp cận xử lý chuỗi (Approach 1) là an toàn và chuẩn mực hơn.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Input N có thể có độ dài rất lớn, do đó bắt buộc phải xử lý N như một chuỗi ký tự (string) thay vì số nguyên.
• Biến đếm số lượng chữ số 5 và 9 (cnt) có giá trị tối đa bằng độ dài của N. Nếu N có 1000 chữ số, cnt tối đa là 1000, hoàn toàn nằm trong phạm vi xử lý của số nguyên cơ bản.

Lỗi thường gặp

• Quên trường hợp số 0: Hàm kiểm tra số may mắn cần xử lý riêng nếu đầu vào là 0 (vì 0 không chứa 5 hoặc 9).
• Sử dụng kiểu số nguyên để lưu N: Nếu N có trên 19 chữ số, unsigned long long cũng không đủ dung lượng, dẫn đến lỗi.