C++-এ বৃহত্তম প্যালিনড্রোম গুণফল

বৃহত্তম প্যালিনড্রোম গুণফল সমস্যা

এই সমস্যায় একটি ইনপুট n দেওয়া থাকে, যা অঙ্কের সংখ্যা নির্দেশ করে। আমাদের কাজ হল দুটি n-অঙ্কের সংখ্যা গুণ করে 만들 수 있는 সর্বোচ্চ প্যালিনড্রোম সংখ্যা খুঁজে বের করা। যেহেতু সংখ্যাগুলো খুব বড় হতে পারে, ফলাফলটি ১৩৩৭ দিয়ে মডুলো করে ফেরত দেওয়া হয়।

উদাহরণস্বরূপ, n = 2 হলে, সবচেয়ে বড় প্যালিনড্রোম হলো ৯০০৯ (৯৯ × ৯১ = ৯০০৯)। ১৩৩৭ দিয়ে মডুলো করলে পাওয়া যায় ৯৮৭।

সমাধানের পদ্ধতি

• maxVal := 10^n - 1 (সর্বোচ্চ n-অঙ্কের সংখ্যা)
• minVal := maxVal / 10 (ন্যূনতম n-অঙ্কের সংখ্যা)
• h = maxVal থেকে minVal+1 পর্যন্ত নিচের দিকে লুপ চালান:
  • left := h, right := 0 নিন
  • h-কে উল্টে right-এ যোগ করুন এবং left-কে ১০ দিয়ে গুণ করুন (এভাবে একটি প্যালিনড্রোম x = left + right তৈরি হবে)
  • i = maxVal থেকে minVal+1 পর্যন্ত লুপ চালান:
    • যদি i < x / i হয়, তবে লুপ থেকে বের হোন
    • যদি x % i == 0 হয়, তবে x % 1337 ফেরত দিন
• যদি কিছুই না মিলে, তবে ৯ ফেরত দিন

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;
}

ইনপুট

3

আউটপুট

123