Hiểu bài toán

Cho một số nguyên lớn được biểu diễn dưới dạng chuỗi ký tự. Nhiệm vụ của bạn là tính tổng các chữ số của số đó. Ví dụ, với số '123', tổng các chữ số là 1 + 2 + 3 = 6. Do số có thể rất lớn, không thể lưu trữ nó dưới dạng số nguyên thông thường mà cần xử lý trực tiếp trên chuỗi ký tự.

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

Cách Duyệt chuỗi và cộng dồn

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;
    long long sum = 0;
    for (char c : s) {
        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 quan nhất. Ta đọc số vào dưới dạng chuỗi s. Sau đó, ta duyệt qua từng ký tự trong chuỗi. Với mỗi ký tự, ta trừ đi mã ASCII của ký tự '0' để lấy giá trị số nguyên tương ứng rồi cộng vào biến tổng. Cuối cùng in ra tổng. Do ta chỉ cần một biến lưu tổng và duyệt qua chuỗi một lần, độ phức tạp thời gian là O(n) (với n là độ dài chuỗi) và bộ nhớ là O(1).

Cách Sử dụng stringstream

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

int main() {
    string s;
    cin >> s;
    int sum = 0;
    for (char c : s) {
        sum += c - '0';
    }
    cout << sum;
    return 0;
}

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

Mặc dù code mẫu sử dụng phương pháp duyệt chuỗi trực tiếp, một cách khác để xử lý đầu vào là sử dụng stringstream để phân tách các số nếu chúng được ngăn cách bởi dấu cách. Tuy nhiên, trong bài toán này với một số duy nhất, cách hiệu quả và phổ biến nhất là duyệt trực tiếp chuỗi ký tự như Solution 1 và 3. Logic tính toán vẫn là chuyển ký tự thành số và cộng dồn.

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

Bài học kinh nghiệm

• Biến một ký tự số (vd: '5') thành giá trị số nguyên (vd: 5) bằng cách lấy mã ASCII của ký tự đó trừ đi mã ASCII của ký tự '0'.
• Bài toán này có thể giải quyết hiệu quả bằng cách chỉ đọc dữ liệu vào dưới dạng chuỗi và xử lý từng phần tử mà không cần quan tâm đến việc số quá lớn để lưu trữ kiểu số nguyên.
• Dữ liệu đầu vào chỉ bao gồm một số nguyên dương (hoặc 0), không có khoảng trắng hay ký tự thừa.

Lỗi thường gặp

• Sử dụng kiểu int hoặc long long để lưu số đầu vào thay vì string, dẫn đến lỗi tràn số (overflow) nếu số đầu vào quá lớn.
• Quên trừ đi '0' khi chuyển đổi ký tự, dẫn đến việc cộng dồn mã ASCII thay vì giá trị số.
• Xử lý sai các ký tự xuống dòng hoặc khoảng trắng nếu sử dụng getline thay vì cin một cách không cẩn thận.