Hiểu bài toán

Bài toán yêu cầu tính 'độ bền' của một số N. Độ bền được định nghĩa là tổng các chữ số của số đó. Quá trình này được lặp lại cho đến khi kết quả chỉ còn một chữ số. Ví dụ: Với N = 19, ta có 1 + 9 = 10, sau đó 1 + 0 = 1. Độ bền của 19 là 1. N có thể có giá trị rất lớn (đến 10^18), do đó cần chú ý đến kiểu dữ liệu và phương pháp tối ưu.

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

Cách Mô phỏng (Brute Force)

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

int main() {
    unsigned long long n;
    cin >> n;
    while (n >= 10) {
        unsigned long long s = 0;
        while (n > 0) {
            s += n % 10;
            n /= 10;
        }
        n = s;
    }
    cout << n;
    return 0;
}

• Time Complexity: O(log N * số lần lặp)
• Space Complexity: O(1)

Phương pháp này sử dụng vòng lặp để mô phỏng chính xác quá trình tính độ bền. Ban đầu, N được đọc vào dưới dạng unsigned long long để xử lý số lớn. Vòng lặp ngoài while (n >= 10) chạy cho đến khi số chỉ còn một chữ số. Bên trong, vòng lặp while (n > 0) tính tổng các chữ số bằng cách lấy số dư 10 (n % 10) và chia lấy nguyên cho 10 (n /= 10). Tổng này được gán lại cho n và quá trình lặp lại. Phương pháp này dễ hiểu và đảm bảo đúng với mọi trường hợp.

Cách Xử lý chuỗi (String Processing)

#include <bits/stdc++.h>
using namespace std;
string s;
int tong;
int main(){
    cin >> s;
    while (s.size() > 1){
        tong = 0;
        for (int i = 0; i < s.size(); i++){
            tong = tong + s[i] - '0';
        }
        s = to_string(tong);
    }
    cout << s << endl;
    return 0;
}

• Time Complexity: O(L * K) (L là độ dài chuỗi, K là số lần lặp)
• Space Complexity: O(L)

Phương pháp này đọc số N dưới dạng chuỗi ký tự. Điều này cho phép xử lý các số cực lớn mà không lo tràn kiểu số nguyên. Trong mỗi bước lặp, chương trình duyệt qua từng ký tự của chuỗi, chuyển đổi nó thành số nguyên (bằng cách trừ '0') và cộng vào biến tổng. Sau đó, biến tổng được chuyển lại thành chuỗi để thực hiện bước tiếp theo. Cách này an toàn về mặt biên độ số nhưng thường chậm và tốn bộ nhớ hơn so với phương pháp số học.

Cách Công thức toán học (Digital Root - Quy tắc chia hết cho 9)

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    if (n == 0) cout << 0;
    else if (n % 9 == 0) cout << 9;
    else cout << n % 9;
    return 0;
}

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

Đây là phương pháp tối ưu nhất, dựa trên định nghĩa toán học của 'Digital Root'. Giá trị độ bền của N (đến khi còn 1 chữ số) chính là giá trị của N modulo 9 (theo công thức số học). Nếu N chia hết cho 9, kết quả là 9 (trừ trường hợp N = 0 thì kết quả là 0). Các trường hợp khác kết quả là N % 9. Phương pháp này chạy tức thời (O(1)) và sử dụng rất ít bộ nhớ, phù hợp nhất với các bài toán quy mô lớn.

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

Bài học kinh nghiệm

• Bài toán này thực chất là tìm 'Digital Root' của số N.
• Nếu N chia hết cho 9 (và N > 0), độ bền là 9.
• Nếu N = 0, độ bền là 0.
• Nếu N không chia hết cho 9, độ bền bằng N % 9.

Lỗi thường gặp

• Sử dụng kiểu dữ liệu quá nhỏ (như int) cho N, trong khi N có thể lên tới 10^18, dẫn đến tràn số (overflow).
• Quên xử lý trường hợp N = 0 đối với phương pháp quy tắc chia hết cho 9 (vì 0 % 9 = 0, nhưng nhiều người thường nhầm lẫn quy tắc 'chia hết cho 9 thì bằng 9').
• Viết lặp vô hạn nếu logic tính tổng sai (ví dụ: không đặt điều kiện dừng đúng trong vòng lặp while).