ผลคูณพาลินโดรมสูงสุดใน C++

ภาพรวมปัญหา

หาผลคูณพาลินโดรม (palindrome) ที่มากที่สุดซึ่งได้จากการคูณเลขสองจำนวนที่มี n หลัก แล้วนำผลลัพธ์มาหารเอาเศษด้วย 1337

ตัวอย่าง

n = 2 → ตัวเลข 2 หลักมากที่สุดคือ 99
99 × 91 = 9009 (เป็นพาลินโดรม)
9009 mod 1337 = 987

วิธีแก้ปัญหา

แทนที่จะลองคูณทุกคู่ (ซึ่งช้า) เราสร้างพาลินโดรมจากตัวเลขมากไปน้อย แล้วตรวจสอบว่าหารด้วยตัวเลข n หลักได้ลงตัวหรือไม่

ขั้นตอนหลัก

1. maxVal = 10^n - 1 (ตัวเลข n หลักมากที่สุด)
2. minVal = maxVal / 10 (ตัวเลข n หลักน้อยที่สุด)
3. วน h จาก maxVal ลง minVal + 1:
   • สร้างพาลินโดรม x จาก h (เช่น h=99 → x=9999)
   • ลองหาร x ด้วย i จาก maxVal ลง minVal + 1
   • ถ้า x % i == 0 และผลหารอยู่ในช่วง n หลัก → คืนค่า x % 1337
4. ถ้าไม่เจอ คืนค่า 9 (กรณี n=1)

โค้ด C++

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;

class Solution {
public:
    int largestPalindrome(int n) {
        int maxVal = pow(10, n) - 1;
        int minVal = maxVal / 10;
        for (int h = maxVal; h > minVal; h--) {
            lli left = h;
            lli right = 0;
            for (lli i = h; i > 0; right = right * 10 + i % 10, left *= 10, i /= 10);
            lli x = left + right;
            for (int i = maxVal; i > minVal; i--) {
                if (i < x / i) break;
                if (x % i == 0) return x % 1337;
            }
        }
        return 9;
    }
};

int main() {
    Solution ob;
    cout << (ob.largestPalindrome(3));
}

การวิเคราะห์ความซับซ้อน

• เวลา: ประมาณ O(10^n) แต่เร็วมากในทางปฏิบัติเพราะ break เร็ว
• พื้นที่: O(1)

การทดสอบ

Input: 3
Output: 123