Editorial for ptit004: Số đơn giản

Hiểu bài toán

Bài toán yêu cầu nén một số N (0 ≤ N ≤ 10^9) về một 'số đơn giản' (chỉ có một chữ số) bằng cách lặp lại thao tác tính tổng các chữ số của số đó cho đến khi kết quả là một số có một chữ số. Ví dụ: 23 -> 2+3=5 (dừng lại), 99 -> 9+9=18 -> 1+8=9 (dừng lại).

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

Cách Phương pháp xử lý số học (Iterative Sum)

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);

    // Lặp lại cho đến khi n là số một chữ số
    while (n >= 10) {
        int sum = 0;
        int temp = n;
        // Tính tổng các chữ số
        while (temp > 0) {
            sum += temp % 10;
            temp /= 10;
        }
        n = sum;
    }

    printf("%d", n);
    return 0;
}

• Time Complexity: O(log N * log(log N)) - Số lần lặp phụ thuộc vào số lượng chữ số, nhưng rất nhỏ (tối đa 2-3 lần cho N ≤ 10^9)
• Space Complexity: O(1) - Chỉ sử dụng biến cục bộ

Approach này sử dụng vòng lặp kép. Vòng lặp ngoài kiểm tra xem số có phải là số đơn giản (n < 10) hay không. Nếu chưa, vòng lặp trong sẽ tách từng chữ số cộng lại để tạo thành số mới. Ví dụ: 99 -> vòng lặp trong tính 9+9=18, gán n=18. Tiếp tục vòng lặp ngoài, 18 >= 10 nên lại tính 1+8=9. Dừng lại và in kết quả.

Cách Phương pháp toán học tối ưu (Direct Division)

#include "stdio.h"

int main () {
    int n = 0; 
    scanf("%d",&n);

    // Trong khi n vẫn là số có 2 chữ số trở lên
    while (n >= 10)
    {
        n = (n / 10) + (n % 10);
    }
    printf("%d", n);
    return 0;
}

• Time Complexity: O(log N) - Tối đa khoảng 3-4 bước tính toán cho N ≤ 10^9
• Space Complexity: O(1) - Không tốn bộ nhớ phụ

Đây là biến thể tối ưu hơn của phương pháp số học. Thay vì dùng vòng lặp trong để tách từng chữ số, ta chỉ cần lấy số hàng chục (n/10) cộng với số hàng đơn vị (n%10). Ví dụ: 99 -> 9 + 9 = 18. Tuy nhiên, cách này chỉ hoạt động chính xác nếu số có đúng 2 chữ số. Để xử lý số nhiều chữ số, ta cần lặp lại nhiều lần. Với N=10^9, sau 2-3 lần lặp, số sẽ trở về dưới 100 và phép tính này sẽ chính xác.

Cách Phương pháp quy hoạch động/Đệ quy

#include <stdio.h>

int tachso(int n){
    int sum = 0;
    while(n){
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

void simple(int n){
    while(n >= 10){
        n = tachso(n);
    }
    printf("%d",n);
}

int main(){
    int n;
    scanf("%d",&n);
    simple(n);
    return 0;
}

• Time Complexity: O(log N) - Tương tự approaches khác
• Space Complexity: O(1) - Hoặc O(log N) nếu đệ quy (đây là iterative)

Approach này tách biệt logic tính tổng các chữ số (hàm tachso) và logic lặp lại (hàm simple). Về bản chất nó giống với Approach 1 nhưng được cấu trúc hóa thành các hàm riêng để dễ đọc và bảo trì code hơn.

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

Bài học kinh nghiệm

• Với N ≤ 10^9, số lần lặp là rất nhỏ (thường chỉ 2-3 lần) nên độ phức tạp time rất thấp.
• Bài toán này thực chất là tìm 'Digital Root' của số N.
• Có thể giải nhanh bằng công thức: Nếu N % 9 == 0 và N != 0 thì kết quả là 9, ngược lại kết quả là N % 9. Tuy nhiên, do yêu cầu mô phỏng quá trình nén, các giải pháp lặp là phù hợp nhất.

Lỗi thường gặp

• Quên xử lý trường hợp N = 0: Kết quả phải là 0. Các vòng lặp while(n>=10) hoặc while(n>0) đều bỏ qua đúng trường hợp này.
• Sử dụng biến kiểu char/mảng ký tự để lưu số lớn: Không cần thiết vì N ≤ 10^9 nằm trong giới hạn của int.
• Lỗi logic với phép chia trực tiếp: Như đã nêu ở Approach 2, việc cộng trực tiếp hàng chục và hàng đơn vị một lần duy nhất cho số lớn sẽ sai kết quả.