ผลิตภัณฑ์ Palindrome ที่ใหญ่ที่สุดใน C++

สมมติว่าเรามีอินพุต n เราต้องหา palindrome ที่ใหญ่ที่สุดที่สามารถสร้างได้โดยใช้การคูณตัวเลขสอง 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) ทำ −
  • ซ้าย :=h, ขวา :=0
  • สำหรับการเริ่มต้น i :=h เมื่อ i> 0, อัปเดต right =right * 10 + i mod 10, left :=left * 10, i :=i / 10, do −
    • x :=ซ้าย + ขวา
    • สำหรับการเริ่มต้น i :=maxVal เมื่อ i> minVal อัปเดต (ลด i โดย 1) ทำ −
      • ถ้าฉัน
      • ออกมาจากวงจร
    • ถ้า x mod i เท่ากับ 0 แล้ว −
      • return x mod 1337

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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