Hiểu bài toán

Bài toán yêu cầu tính tổng các chữ số của một số nguyên dương N có độ dài lên tới 255 chữ số. Đầu vào là một chuỗi ký tự số N, đầu ra là tổng M của tất cả các chữ số trong N. Ví dụ: N = 84915388247 thì tổng các chữ số là 8+4+9+1+5+3+8+8+2+4+7 = 59.

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

Cách Xử lý chuỗi cơ bản

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

int main() {
    string s;
    cin >> s;

    long long sum = 0;
    for (char c : s) {
        if (c >= '0' && c <= '9')
            sum += (c - '0');
    }

    cout << sum;
    return 0;
}

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

Đây là cách tiếp cận trực tiếp nhất. Đọc N vào dưới dạng chuỗi, duyệt qua từng ký tự trong chuỗi, kiểm tra xem có phải là chữ số không, sau đó chuyển đổi từ ký tự sang số nguyên và cộng dồn vào biến tổng. Biến tổng dùng kiểu long long để đề phòng tổng quá lớn (tối đa 255*9 = 2295, nhưng dùng long long vẫn an toàn).

Cách Tối ưu với cin.tie

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

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

    string N;
    cin >> N;
    int sum = 0;
    for (char c : N) {
        if (c >= '0' && c <= '9') {
            sum += c - '0';
        }
    }
    cout << sum;
    return 0;
}

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

Giống cách trên nhưng thêm các tối ưu hóa nhập xuất: ios::syncwithstdio(false) và cin.tie(nullptr) để tăng tốc độ đọc dữ liệu. Ở đây dùng int cho biến sum vì tổng tối đa chỉ là 2295, tiết kiệm bộ nhớ hơn long long.

Cách Sử dụng hàm isdigit

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string N;
    cin >> N;

    long long M = 0;
    for (char c : N)
    {
        if (isdigit(c))
            M += c - '0';
    }

    cout << M;
}

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

Cách tiếp cận tương tự nhưng sử dụng hàm isdigit(c) từ thư viện <cctype> (đã bao gồm trong bits/stdc++.h) để kiểm tra xem ký tự có phải là chữ số hay không. Hàm này thường được dùng để tăng tính readable của code.

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

Bài học kinh nghiệm

• Vì N có thể có đến 255 chữ số, không thể lưu vào kiểu số nguyên thông thường (long long chỉ chứa tối đa ~18-19 chữ số). Do đó, bắt buộc phải xử lý N dưới dạng chuỗi (string).
• Tổng các chữ số của một số có độ dài L tối đa là L*9. Với L=255, tổng tối đa là 2295, nên biến lưu kết quả chỉ cần kiểu int hoặc short là đủ.
• Phép chuyển đổi từ ký tự số sang giá trị số nguyên được thực hiện bằng cách trừ đi ký tự '0'.

Lỗi thường gặp

• Cố gắng đọc N vào biến số nguyên (int, long long, unsigned long long)导致 overflow vì N quá lớn.
• Quên kiểm tra điều kiện input (ví dụ ký tự rác) mặc dù đề bài cho phép N là số nguyên dương, nhưng việc kiểm tra '0' <= c <= '9' là thói quen tốt.
• Sử dụng biến tổng quá nhỏ (ví dụ char) có thể gây tràn số nếu không tính toán trước.