मान लीजिए हमारे पास इनपुट n है, हमें दो n-अंकीय संख्याओं के गुणनफल से बनने वाला सबसे बड़ा पालिंड्रोम ढूंढना है। चूंकि संख्याएं बहुत बड़ी होती हैं, हम 1337 से मोड्यूलो कर सकते हैं। तो यदि इनपुट 2 है, तो उत्तर 987 होगा, 987 = (99*91) mod 1337 = 9009 mod 1337 = 987।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
- maxVal := 10^n - 1
- minVal := maxVal / 10
- h := maxVal से आरंभ करें, जब h > minVal, अपडेट करें (h को 1 से घटाएं), करें -
- left := h, right := 0
- i := h से आरंभ करें, जब i > 0, अपडेट करें right = right * 10 + i mod 10, left := left * 10, i := i / 10, करें -
- x := left + right
- i := maxVal से आरंभ करें, जब i > minVal, अपडेट करें (i को 1 से घटाएं), करें -
- यदि i < x / i, तो -
- लूप से बाहर आएं
- यदि x mod i 0 के समान है, तो -
- x mod 1337 लौटाएं
- यदि i < x / i, तो -
- 9 लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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; } }; main(){ Solution ob; cout << (ob.largestPalindrome(3)); }इनपुट
3
आउटपुट
123
