Hiểu bài toán

Bài toán yêu cầu nhập vào một số nguyên dương n (0 < n < 10^8). Nhiệm vụ là tính và in ra tổng các chữ số chẵn và tổng các chữ số lẻ của n, mỗi tổng trên một dòng riêng. Ví dụ, với n = 1234, các chữ số chẵn là 2 và 4 (tổng là 6), các chữ số lẻ là 1 và 3 (tổng là 4).

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

Cách Duyệt từng chữ số bằng phép chia lấy dư

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

int main() {
    long long n;
    cin >> n;
    long long sum_even = 0, sum_odd = 0;

    while (n > 0) {
        int digit = n % 10;
        if (digit % 2 == 0) {
            sum_even += digit;
        } else {
            sum_odd += digit;
        }
        n /= 10;
    }

    cout << sum_even << "\n" << sum_odd;
    return 0;
}

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

Đây là cách tiếp cận trực quan và hiệu quả nhất. Ta sử dụng vòng lặp while để lặp cho đến khi n bằng 0. Trong mỗi bước lặp:

1. Lấy chữ số cuối cùng của n bằng phép chia lấy dư cho 10 (n % 10)
2. Kiểm tra xem chữ số đó có chẵn hay lẻ bằng phép chia lấy dư cho 2
3. Cộng chữ số vào biến tổng tương ứng
4. Loại bỏ chữ số cuối cùng khỏi n bằng phép chia nguyên cho 10 (n /= 10) Cách này xử lý trực tiếp trên số nguyên, rất nhanh và dùng ít bộ nhớ.

Cách Xử lý chuỗi ký tự

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

int main() {
    string s;
    cin >> s;
    long long sum_even = 0, sum_odd = 0;

    for (char c : s) {
        int digit = c - '0';
        if (digit % 2 == 0) {
            sum_even += digit;
        } else {
            sum_odd += digit;
        }
    }

    cout << sum_even << "\n" << sum_odd;
    return 0;
}

• Time Complexity: O(log n) - Số ký tự trong chuỗi bằng số chữ số của n
• Space Complexity: O(log n) - Cần lưu trữ chuỗi chứa các chữ số

Phương pháp này chuyển số n thành chuỗi ký tự, sau đó duyệt qua từng ký tự:

1. Chuyển đổi ký tự thành số nguyên bằng cách trừ '0'
2. Kiểm tra chẵn lẻ và cộng vào tổng tương ứng Cách này dễ đọc và dễ hiểu, đặc biệt hữu ích khi cần xử lý các thao tác phức tạp với từng chữ số. Tuy nhiên, nó tốn thêm bộ nhớ để lưu chuỗi và có thể chậm hơn một chút do việc chuyển đổi kiểu.

Cách Đệ quy

#include <iostream>
using namespace std;

void sumDigits(long long n, long long &sum_even, long long &sum_odd) {
    if (n == 0) return;

    int digit = n % 10;
    if (digit % 2 == 0) {
        sum_even += digit;
    } else {
        sum_odd += digit;
    }

    sumDigits(n / 10, sum_even, sum_odd);
}

int main() {
    long long n;
    cin >> n;
    long long sum_even = 0, sum_odd = 0;

    sumDigits(n, sum_even, sum_odd);

    cout << sum_even << "\n" << sum_odd;
    return 0;
}

• Time Complexity: O(log n) - Đệ quy qua số lượng chữ số
• Space Complexity: O(log n) - Chiều sâu của ngăn xếp đệ quy

Sử dụng đệ quy để xử lý từng chữ số:

1. Hàm đệ quy nhận vào số n và hai tham chiếu đến tổng chẵn và lẻ
2. Điều kiện dừng: n = 0
3. Trong mỗi lần gọi: lấy chữ số cuối, cập nhật tổng, gọi đệ quy với n/10 Phương pháp này thể hiện tính đệ quy nhưng không hiệu quả bằng vòng lặp trong thực tế do tốn kém hơn về mặt bộ nhớ và có thể gây tràn ngăn xếp với số rất lớn (dù trong bài này không đáng kể).

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

Bài học kinh nghiệm

• Vấn đề có thể được giải quyết bằng cách chia tách số thành từng chữ số bằng phép chia lấy dư 10
• Số chữ số của n là log10(n), do đó độ phức tạp thời gian là O(log n) rất nhỏ (tối đa 8 với giới hạn đề bài)
• Có thể sử dụng nhiều cách tiếp cận: trực tiếp trên số nguyên, xử lý chuỗi, hoặc đệ quy

Lỗi thường gặp

• Quên xử lý trường hợp n = 0 (với đề bài này n luôn > 0 nên không phải vấn đề, nhưng trong các biến thể có thể cần xử lý)
• Sử dụng biến sai kiểu (ví dụ int thay vì long long) có thể gây tràn số nếu tính tổng vượt quá giới hạn
• Đặt điều kiện lặp sai (ví dụ while(n != 0) thay vì while(n > 0) có thể gây vòng lặp vô hạn với số âm)
• Quên in xuống dòng giữa hai tổng theo yêu cầu đề bài