Hiểu bài toán

Bài toán yêu cầu kiểm tra xem một số nguyên dương $n$ (với $1 \le n \le 10^{18}$) có chữ số đầu tiên và chữ số cuối cùng giống nhau hay không. Dữ liệu đầu vào gồm nhiều dòng, mỗi dòng chứa một số $n$, và cần in ra 'YES' nếu điều kiện thỏa mãn, 'NO' nếu ngược lại cho mỗi số.

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

Cách String

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

int main() {
    char s[25];
    while (scanf("%s", s) == 1) {
        if (s[0] == s[strlen(s) - 1]) {
            printf("YES\n");
        } else {
            printf("NO\n");");
        }
    }
    return 0;
}

• Time Complexity: O(L) với L là độ dài chuỗi số (rất nhỏ, tối đa ~18)
• Space Complexity: O(L)

Đây là cách tiếp cận trực quan nhất. Do số $n$ có thể lên tới $10^{18}$, nó không thể lưu vừa vào các kiểu dữ liệu số nguyên cơ bản trong một số ngôn ngữ cũ hoặc để xử lý dễ dàng, ta nhập số đó dưới dạng chuỗi ký tự (string). Sau đó, ta chỉ cần so sánh ký tự đầu tiên (s[0]) với ký tự cuối cùng (s[strlen(s) - 1]). Nếu chúng bằng nhau, in 'YES', ngược lại in 'NO'.

Cách Math

#include <stdio.h>
#include <math.h>

int main() {
    long long n;
    while (scanf("%lld", &n) == 1) {
        // Tìm chữ số cuối
        int last = n % 10;

        // Tìm chữ số đầu
        int first = 0;
        long long temp = n;
        while (temp > 0) {
            first = temp % 10;
            temp /= 10;
        }

        if (first == last) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

• Time Complexity: O(log n) (số lần lặp bằng số chữ số)
• Space Complexity: O(1)

Cách này xử lý số dưới dạng toán học. Chữ số cuối cùng lấy được很容易 qua phép chia lấy dư cho 10 (n % 10). Để lấy chữ số đầu tiên, ta dùng một vòng lặp chia dần số cho 10 (n /= 10) cho đến khi số chỉ còn một chữ số. Phương pháp này dùng ít bộ nhớ hơn (không cần mảng ký tự) nhưng code phức tạp hơn một chút.

Cách String with Custom IO

#include <stdio.h>

int main() {
    char c;
    int len = 0;
    char first = 0, last = 0;

    while ((c = getchar()) != EOF) {
        if (c >= '0' && c <= '9') {
            if (len == 0) first = c;
            last = c;
            len++;
        } else {
            if (len > 0) {
                if (first == last) printf("YES\n");
                else printf("NO\n");
                len = 0;
            }
        }
    }
    // Xử lý số cuối cùng nếu file kết thúc mà không có ký tự xuống dòng
    if (len > 0) {
        if (first == last) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

• Time Complexity: O(N) (tổng số ký tự đầu vào)
• Space Complexity: O(1)

Đây là biến thể tối ưu hóa bộ nhớ, đọc input ký tự từng ký tự (streaming) thay vì đọc cả dòng/cả chuỗi. Nó chỉ cần lưu lại ký tự đầu tiên và ký tự cuối cùng của số hiện tại, cùng với trạng thái độ dài. Cách này cực kỳ hiệu quả về bộ nhớ và xử lý được input rất lớn không giới hạn kích thước chuỗi.

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

Bài học kinh nghiệm

• Bài toán chỉ quan tâm đến hai chữ số đầu và cuối, không cần quan tâm đến các chữ số ở giữa.
• Việc nhập số dưới dạng chuỗi (string) là cách đơn giản nhất để tránh tràn số (overflow) đối với số có giới hạn $10^{18}$, và cũng giúp truy cập trực tiếp vào ký tự đầu và cuối.
• Phép chia lấy dư (modulo) là công cụ để lấy chữ số cuối cùng của một số.

Lỗi thường gặp

• Quên kiểm tra trường hợp số chỉ có một chữ số (ví dụ: 5). Trong trường hợp này, chữ số đầu và cuối là một, kết quả luôn là YES. Các giải pháp trên đều xử lý đúng.
• Sử dụng kiểu int hoặc long (32-bit) để lưu $n$ khi $n$ có thể lên tới $10^{18}$, dẫn đến lỗi tràn số. Nên dùng long long (64-bit) hoặc kiểu chuỗi.
• Xử lý sai input cuối file (EOF) hoặc các ký tự whitespace thừa.