ซูเปอร์พาลินโดรมใน C++

คำอธิบายปัญหา

จำนวนเต็มบวก N เรียกว่า superpalindrome ถ้า N เป็น palindrome และ N เป็นกำลังสองของ palindrome อีกตัว หาจำนวน superpalindrome ในช่วง [L, R]

ตัวอย่าง

L=5, R=500 → Output: 3 (คือ 9, 121, 484)

ข้อสังเกต

• ถ้า x² เป็น palindrome และ x เป็น palindrome → x² เป็น superpalindrome
• x ≤ √R ≤ 10⁹ (ถ้า R ≤ 10¹⁸) → x มีได้สูงสุด 9 หลัก
• Palindrome ยาวสูงสุด 9 หลัก สร้างได้ไม่เยอะ (ประมาณ 2×10⁵ ตัว)

แนวทางแก้ปัญหา: Generate Palindromes

1. สร้าง palindrome ทุกตัวที่เป็นไปได้ (ความยาว 1 ถึง 9 หลัก)
2. สำหรับแต่ละ palindrome x คำนวณ x² ตรวจสอบว่าเป็น palindrome และอยู่ในช่วง [L,R]
3. นับจำนวน

การสร้าง Palindrome

• ความยาวคี่: เลือกครึ่งแรก + ตัวกลาง + mirror
• ความยาวคู่: เลือกครึ่งแรก + mirror
• ใช้ recursion/helper function สร้างแบบเพิ่มความยาวทีละ 2

ตัวอย่างโค้ด C++

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

class Solution {
    int ans = 0;
    
    bool isPalindrome(long x) {
        if(x == 0) return true;
        if(x % 10 == 0) return false;
        long l = x, r = 0;
        while(l >= r) {
            if(l == r || l/10 == r) return true;
            r = r*10 + l%10; l /= 10;
        }
        return false;
    }
    
    void helper(long x, int len, int maxLen, long double lb, long double ub) {
        if(x > ub) return;
        if(x >= lb && isPalindrome(x*x)) ans++;
        for(int i=1; len+2*i <= maxLen; i++) {
            long W = pow(10, len+2*i-1) + 1;
            long w = pow(10, i);
            for(int z=1; z<=9; z++)
                helper(z*W + x*w, len+2*i, maxLen, lb, ub);
        }
    }
    
public:
    int superpalindromesInRange(string L, string R) {
        long double lb = sqrt(stol(L)), ub = sqrt(stol(R));
        int maxLen = log10(ub) + 1;
        for(int z=0; z<=9; z++) {
            helper(z, 1, maxLen, lb, ub);
            helper(11*z, 2, maxLen, lb, ub);
        }
        return ans;
    }
};

ความซับซ้อน

• เวลา: O(จำนวน palindrome ≤ √R) ~ O(10⁵)
• พื้นที่: O(log R) สำหรับ recursion