Hiểu bài toán

Bài toán yêu cầu kiểm tra một số tự nhiên N có phải là "số đẹp" hay không. Một số được gọi là đẹp nếu tổng các chữ số của nó, khi chia cho 10, có số dư bằng 9 (tức là tổng các chữ số kết thúc bằng chữ số 9). Ví dụ, với N=27, tổng các chữ số là 2+7=9, chia 10 dư 9 -> YES. Với N=111, tổng là 3, chia 10 dư 3 -> NO.

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

Cách Tính tổng các chữ số bằng toán tử modulo

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

int main() {
    long long n;
    cin >> n;
    long long sum = 0;
    while (n > 0) {
        sum += n % 10; // Lấy chữ số cuối
        n /= 10;       // Bỏ chữ số cuối
    }
    if (sum % 10 == 9) cout << "YES";
    else cout << "NO";
    return 0;
}

• Time Complexity: O(log10(N)) - Số lần lặp bằng số chữ số của N (tối đa ~10~)
• Space Complexity: O(1) - Chỉ sử dụng vài biến lưu trữ

Đây là cách tiếp cận trực quan nhất. Ta sử dụng vòng lặp while để lặp qua từng chữ số của N. Trong mỗi bước lặp, n % 10 cho biết chữ số cuối cùng, ta cộng nó vào biến tổng sum. Sau đó, n /= 10 loại bỏ chữ số vừa lấy đi. Khi n trở về 0, vòng lặp kết thúc và sum chứa tổng các chữ số. Cuối cùng chỉ cần kiểm tra điều kiện sum % 10 == 9.

Cách Cách tiếp cận hướng đối tượng (OOP)

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

class SODEPN {
private:
    long long n;
public:
    void Nhap() {
        cin >> n;
    }
    void Tinh() {
        long long sum = 0;
        long long temp = n; // Dùng biến tạm để không thay đổi n gốc
        while (temp > 0) {
            sum += temp % 10;
            temp /= 10;
        }
        if (sum % 10 == 9) cout << "YES";
        else cout << "NO";
    }
};

int main() {
    SODEPN x;
    x.Nhap();
    x.Tinh();
    return 0;
}

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

Cách này sử dụng lớp (class) để đóng gói dữ liệu và hành động. Logic tính tổng các chữ số vẫn giống cách 1, nhưng được tổ chức dưới dạng phương thức của lớp. Đây là cách tốt để rèn luyện lập trình hướng đối tượng, dù hơi dư thừa cho bài toán đơn giản này. Lưu ý dùng biến temp để tránh thay đổi giá trị biến thành viên n.

Cách Dùng biến toàn cục (Global Variable)

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

ll n, s = 0;

int main() {
    cin >> n;
    while (n != 0) {
        s += n % 10;
        n /= 10;
    }
    if (s % 10 == 9) cout << "YES";
    else cout << "NO";
    return 0;
}

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

Cách này khai báo biến n và s ở phạm vi toàn cục. Logic tính tổng tương tự như cách 1. Đây là cách viết ngắn gọn thường thấy trong lập trình thi đấu tốc độ cao, nhưng về mặt kỹ thuật, việc dùng biến toàn cục có thể gây ra xung đột tên biến trong các bài toán lớn hơn hoặc khi kết hợp nhiều file.

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

Bài học kinh nghiệm

• Bài toán chỉ quan tâm đến tổng các chữ số modulo 10, nên không cần quan tâm nếu tổng vượt quá 9.
• Số N tối đa là 10^9, tức là có tối đa 10 chữ số, nên độ phức tạp O(log N) là cực kỳ nhanh (chỉ vài bước lặp).

Lỗi thường gặp

• Quên xử lý trường hợp N = 0: Nếu N = 0, vòng lặp while (n > 0) sẽ không chạy, sum = 0. 0 % 10 = 0 != 9 -> Output NO (Đúng theo đề bài).
• Sử dụng biến n gốc để lặp trực tiếp: Nếu không muốn thay đổi giá trị n ban đầu (phục vụ cho việc in ra hoặc xử lý sau này), nên dùng một biến tạm (ví dụ: temp = n).