Số Palindrome cơ số kép (Double Base Palindrome) trong C++

Giới thiệu

Số Palindrome cơ số kép là số mà biểu diễn của nó trong hệ thập phân (cơ số 10) VÀ trong một cơ số khác cho trước (ví dụ nhị phân - cơ số 2) đều là palindrome (đọc xuôi ngược đều giống nhau).

Ví dụ

Số 313:

• Cơ số 10: 313 → Palindrome ✓
• Cơ số 2: 100111001 → Palindrome ✓

→ 313 là Double Base Palindrome

Mã nguồn hoàn chỉnh

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

string integer_to_string(int n, int base) {
    string str;
    while (n > 0) {
        int digit = n % base;
        n /= base;
        str.push_back(digit + '0');
    }
    return str;
}

string isDoubleBasePalindrome(int n, int k) {
    // Kiểm tra palindrome trong cơ số 10
    int temp = n;
    int reversed = 0;
    while (temp > 0) {
        reversed = temp % 10 + reversed * 10;
        temp /= 10;
    }
    
    if (reversed == n) {
        // Chuyển sang cơ số k
        string str = integer_to_string(n, k);
        string reversed_str = str;
        reverse(reversed_str.begin(), reversed_str.end());
        
        if (str == reversed_str) {
            return "Yes";
        }
    }
    return "No";
}

int main() {
    int n = 313, k = 2;
    cout << isDoubleBasePalindrome(n, k) << endl;
    return 0;
}

Kết quả chạy chương trình

Yes

Một số số Double Base Palindrome nổi tiếng

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

• Thời gian: O(log_kn + log₁₀n) - chuyển đổi cơ số và kiểm tra palindrome
• Không gian: O(log_kn) - lưu chuỗi biểu diễn trong cơ số k

Lưu ý quan trọng

Hàm integer_to_string trả về chuỗi ngược (LSB trước). Do đó việc so sánh với chuỗi đảo ngược vẫn đúng vì palindrome đọc xuôi ngược đều giống nhau.

Kết luận

Bài toán kết hợp kiểm tra palindrome và chuyển đổi cơ số, là bài tập tốt để thực hành thao tác chuỗi và hệ cơ số trong C++.