Đề bài

Cho một số nguyên x, hãy xác định xem nó có phải là số đối xứng hay không. Một số được gọi là đối xứng nếu đọc từ trái sang phải hay từ phải sang trái đều cho cùng một giá trị. Ví dụ: 121 là số đối xứng, trong khi 123 thì không.

Ví dụ minh họa

• Ví dụ 1:
  Đầu vào: x = 121
  Đầu ra: true
• Ví dụ 2:
  Đầu vào: x = -121
  Đầu ra: false
  Giải thích: Số âm không thể là số đối xứng do dấu trừ chỉ xuất hiện ở một đầu.
• Ví dụ 3:
  Đầu vào: x = 10
  Đầu ra: false
  Giải thích: Đảo ngược thành "01", tức là 1, khác với 10.

Phân tích và chiến lược giải

Nhiều người lập trình viên nghĩ ngay đến việc chuyển số thành chuỗi rồi so sánh thuận và đảo. Tuy nhiên, cách này sử dụng cấu trúc dữ liệu phụ (chuỗi), không tối ưu về mặt ý tưởng toán học.

Một hướng tiếp cận thông minh hơn là **chỉ đảo nửa sau của số** và so sánh với nửa đầu. Điều này giúp tránh rủi ro tràn số (overflow) khi đảo toàn bộ — đặc biệt quan trọng trong các ngôn ngữ như C++ với giới hạn kiểu dữ liệu rõ ràng.

Ý tưởng chính

• Nếu x < 0, chắc chắn không phải số đối xứng.
• Nếu chữ số cuối là 0 (tức x % 10 == 0), thì để đối xứng, chữ số đầu cũng phải là 0 — điều chỉ đúng với số 0. Vậy mọi số chia hết cho 10 (trừ 0) đều loại.
• Chúng ta sẽ lần lượt lấy từng chữ số cuối của x để xây dựng số đảo ngược, nhưng chỉ làm đến khi phần đảo ngược lớn hơn hoặc bằng phần còn lại của x.
• Sau vòng lặp:
  • Nếu độ dài số là chẵn: so sánh trực tiếp x == reverted.
  • Nếu độ dài số là lẻ: bỏ qua chữ số ở giữa bằng cách so sánh x == reverted / 10.

Cách triển khai hiệu quả

class Solution {
public:
    bool isPalindrome(int x) {
        // Loại bỏ trường hợp âm và số kết thúc bằng 0 (trừ số 0)
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int reversedHalf = 0;
        while (x > reversedHalf) {
            reversedHalf = reversedHalf * 10 + x % 10;
            x /= 10;
        }

        // So sánh x với nửa đảo ngược (xử lý cả trường hợp số lẻ chữ số)
        return x == reversedHalf || x == reversedHalf / 10;
    }
};

Giải thích thêm về xử lý số lẻ chữ số

Xét ví dụ 12321:

• Sau mỗi bước, x giảm dần, reversedHalf tăng dần.
• Kết thúc vòng lặp: x = 12, reversedHalf = 123.
• Chữ số giữa là 3 — không ảnh hưởng đến tính đối xứng. Ta loại nó bằng cách chia reversedHalf cho 10.
• So sánh: 12 == 123 / 10 → 12 == 12 → đúng.

Tại sao không đảo toàn bộ?

Một cách tiếp cận đơn giản là đảo toàn bộ số rồi so sánh:

// Cách này dễ bị tràn số!
long long reversed = 0;
int original = x;
while (x > 0) {
    reversed = reversed * 10 + x % 10;
    x /= 10;
}
return reversed == original;

Tuy nhiên, nếu số rất lớn (gần INT_MAX), việc đảo ngược có thể vượt quá giới hạn kiểu int. Dù dùng long long có thể cứu vãn, nhưng vẫn không cần thiết và tốn bộ nhớ.

Độ phức tạp

• Thời gian: O(log n) — vì chúng ta xử lý khoảng một nửa số chữ số.
• Không gian: O(1) — chỉ dùng biến đếm và biến lưu giá trị đảo.