Tích palindrome lớn nhất trong C++

Cho số nguyên n, tìm palindrome lớn nhất có thể tạo được từ tích của hai số có n chữ số. Kết quả lấy modulo 1337.

Ví dụ

Với n = 2: palindrome lớn nhất là 9009 = 99 × 91. Kết quả: 9009 % 1337 = 987.

Thuật toán

Thay vì duyệt tất cả cặp số (quá chậm), ta sinh các palindrome theo thứ tự giảm dần và kiểm tra xem có thể phân tích thành tích của hai số n chữ số hay không.

1. Xác định phạm vi: maxVal = 10^n - 1, minVal = maxVal / 10.
2. Duyệt h từ maxVal xuống minVal + 1:
   • Tạo palindrome x bằng cách gắn ngược h vào cuối h (ví dụ: h = 91 → x = 9119).
   • Kiểm tra xem x có chia hết cho số i nào trong khoảng [maxVal, minVal] sao cho thương cũng trong khoảng đó.
   • Nếu tìm thấy, trả về x % 1337.
3. Nếu không tìm thấy (trường hợp n = 1), trả về 9.

Cài đặt 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);
    return 0;
}

Độ phức tạp

• Thời gian: ~O(10^n) trong trường hợp xấu, nhưng thực tế dừng sớm nhờ break khi i < x/i.
• Không gian: O(1).

Input / Output

Input:  3
Output: 123