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. Với T test case, mỗi test case cung cấp một số n (1 ≤ n ≤ 10^18), nhiệm vụ là xuất ra tổng các chữ số của n.

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

Cách Xử lý số học

#include <stdio.h>

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        long long n;
        scanf("%lld", &n);
        int sum = 0;
        while (n > 0) {
            sum += n % 10;
            n /= 10;
        }
        printf("%d\n", sum);
    }
    return 0;
}

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

Phương pháp này sử dụng các phép toán số học để lấy từng chữ số. Vòng lặp 'while (n > 0)' thực hiện: 1. Lấy chữ số hàng đơn vị bằng 'n % 10' và cộng vào tổng. 2. Loại bỏ chữ số hàng đơn vị bằng 'n /= 10'. Quá trình lặp lại cho đến khi n bằng 0. Với n <= 10^18, số lượng chữ số tối đa là 19, nên số bước lặp là hằng số rất nhỏ.

Cách Xử lý chuỗi

#include <stdio.h>
#include <string.h>

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        char n[25];
        scanf("%s", n);
        int sum = 0;
        for (int i = 0; n[i] != '\0'; i++) {
            sum += n[i] - '0';
        }
        printf("%d\n", sum);
    }
    return 0;
}

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

Phương pháp này đọc số n dưới dạng chuỗi ký tự. Vòng lặp duyệt qua từng ký tự trong chuỗi, chuyển đổi ký tự số tương ứng thành giá trị số nguyên (bằng cách trừ đi '0') và cộng vào tổng. Độ dài L của chuỗi phụ thuộc vào giá trị của n (tối đa ~19 ký tự). Phương pháp này an toàn với số rất lớn nhưng tốn bộ nhớ hơn một chút.

Cách Đọc và xử lý chuỗi với fgets

#include <stdio.h>
#include <string.h>

int main() {
    int T;
    scanf("%d", &T);
    getchar();
    char a[25];
    while (T--) {
        fgets(a, sizeof(a), stdin);
        int n = strlen(a);
        if (a[n - 1] == '\n') {
            a[n - 1] = '\0';
            --n;
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += a[i] - '0';
        }
        printf("%d\n", sum);
        --T;
    }
}

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

Đây là biến thể của phương pháp xử lý chuỗi, sử dụng 'fgets' để đọc input. Cần xử lý ký tự newline kết thúc chuỗi. Lợi ích của fgets là xử lý input dòng tốt hơn scanf, tránh tràn bộ đệm trong một số trường hợp.

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

Bài học kinh nghiệm

• Với giới hạn n ≤ 10^18, số lượng chữ số rất nhỏ (tối đa 19), nên cả hai phương pháp số học và chuỗi đều chạy cực nhanh và hiệu quả.
• Phương pháp số học (modulo và chia) thường được ưu tiên do không cần cấp phát bộ nhớ động cho chuỗi và logic đơn giản.
• Phương pháp chuỗi hữu ích nếu số đầu vào quá lớn vượt quá kiểu dữ liệu số nguyên (ví dụ: > 10^19), dù trong bài này không yêu cầu.

Lỗi thường gặp

• Quên xóa ký tự newline ('\n') khi đọc chuỗi bằng fgets, dẫn đến lỗi tính toán nếu ký tự này được xử lý như số.
• Sử dụng kiểu int hoặc long để lưu n khi n > 10^9, gây tràn số. Trong bài này n có thể lên tới 10^18, bắt buộc dùng long long.
• Trong phương pháp số học, cần đảm bảo vòng lặp xử lý đúng với n = 0 (nếu đầu vào cho phép n=0). Tuy nhiên bài này n ≥ 1 nên không phải vấn đề.