Hiểu bài toán

Bài toán yêu cầu nhập một mảng gồm n số nguyên và in ra các số Palindrome theo đúng thứ tự nhập. Số Palindrome là số đọc từ trái qua phải hay từ phải qua trái đều giống nhau (ví dụ: 121, 1331). Ràng buộc quan trọng là không được dùng các thao tác chuỗi (string manipulation) để xử lý logic kiểm tra. Tuy nhiên, việc chuyển đổi sang chuỗi chỉ để in ra kết quả là có thể chấp nhận được. Input n ≤ 1000 và các số ≤ 10^9.

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

Cách Chuyển đổi chuỗi (String Conversion)

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

bool pl(int n) {
    string s = to_string(n);
    string rs = s;
    reverse(rs.begin(), rs.end());
    return s == rs;
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        if (pl(x)) {
            cout << x << ' ';
        }
    }
    return 0;
}

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

Đây là cách tiếp cận trực quan nhất. Hàm pl chuyển số nguyên thành chuỗi, tạo một bản sao đảo ngược của chuỗi đó và so sánh chúng. Nếu chúng giống nhau, số đó là Palindrome. Độ phức tạp phụ thuộc vào độ dài L của số (tối đa 10 chữ số).

Cách Xử lý số học (Mathematical Reversal)

#include <iostream>
using namespace std;

bool isPalindrome(int n) {
    if (n < 0) return false;
    int original = n;
    long long reversed = 0;
    while (n > 0) {
        reversed = reversed * 10 + n % 10;
        n /= 10;
    }
    return original == reversed;
}

int main() {
    int n;
    cin >> n;
    int x;
    for (int i = 0; i < n; i++) {
        cin >> x;
        if (isPalindrome(x)) {
            cout << x << ' ';
        }
    }
    return 0;
}

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

Phương pháp này tuân thủ nghiêm ngặt yêu cầu 'không dùng chuỗi'. Nó tạo ra một số mới bằng cách lặp qua các chữ số của số cũ (lấy số cuối cùng và nhân với 10). Nếu số mới tạo ra bằng số ban đầu, nó là Palindrome. Lưu ý dùng long long cho biến reversed để tránh tràn số (overflow) khi xử lý số lớn (ví dụ 10^9).

Cách So sánh trực tiếp từng cặp chữ số (Two-pointer Math)

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

bool check(int n) {
    if (n < 0) return false;
    if (n == 0) return true;

    int len = 0;
    int temp = n;
    while (temp > 0) {
        len++;
        temp /= 10;
    }

    int div = pow(10, len - 1);

    while (n > 0) {
        int left = n / div;
        int right = n % 10;
        if (left != right) return false;
        n = (n % div) / 10;
        div /= 100;
    }
    return true;
}

int main() {
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        if (check(x)) cout << x << ' ';
    }
    return 0;
}

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

Phương pháp này so sánh trực tiếp chữ số đầu tiên và cuối cùng, rồi bỏ đi 2 chữ số đó và lặp lại. Nó tìm độ dài số (số chữ số) bằng cách chia liên tục cho 10, sau đó dùng bộ chia (divisor) để lấy chữ số đầu tiên. Đây là cách hiệu quả về mặt toán học và tránh việc tạo ra một số đảo ngược hoàn toàn.

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

Bài học kinh nghiệm

• Yêu cầu 'không dùng thao tác chuỗi' là để kiểm tra logic Palindrome, chứ không cấm dùng chuỗi khi in kết quả (mặc dù in số nguyên trực tiếp là tốt nhất).
• Các số Palindrome có tính đối xứng, nên ta có thể so sánh cặp chữ số đầu và cuối (xử lý số học) hoặc tạo số đảo ngược.
• Vì các số đầu vào ≤ 10^9 (tối đa 10 chữ số), việc lưu số đảo ngược vào kiểu long long là an toàn để tránh tràn số.

Lỗi thường gặp

• Tràn số (Integer Overflow): Nếu chỉ dùng int để lưu số đảo ngược, số 1.000.000.000 khi đảo ngược sẽ thành 1000000000 (vừa đúng) nhưng nếu lớn hơn tí nữa hoặc dùng phép nhân 10 sai cách có thể bị lỗi. Nên dùng long long cho biến lưu số đảo ngược.
• Xử lý số 0: Nếu vòng lặp while(n > 0) không xử lý đúng trường hợp input là 0, đầu ra có thể bị trống.
• Chuỗi Output: Đảm bảo in các số Palindrome cách nhau bởi dấu cách và không có dấu cách thừa ở cuối dòng (nếu dùng cout << x << ' ' thì sẽ có dấu cách thừa ở cuối, nhưng trong nhiều kỳ thi CP điều này được chấp nhận hoặc có thể xử lý bằng cờ).