Sản phẩm Palindrome lớn nhất trong C ++

Giả sử chúng ta có đầu vào là n, chúng ta phải tìm palindrome lớn nhất có thể được thực hiện bằng phép nhân hai số n chữ số. Vì số lượng rất lớn, chúng ta có thể thực hiện mod bằng cách sử dụng 1337. Vì vậy, nếu đầu vào là 2, thì câu trả lời sẽ là 987, 987 =(99 * 91) mod 1337 =9009 mod 1337 =987.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• maxVal:=10 ^ n - 1
• minVal:=maxVal / 10
• để khởi tạo h:=maxVal, khi h> minVal, hãy cập nhật (giảm h đi 1), thực hiện -
  • left:=h, right:=0
  • để khởi tạo i:=h, khi i> 0, cập nhật right =right * 10 + i mod 10, left:=left * 10, i:=i / 10, do -
    • x:=left + right
    • để khởi tạo i:=maxVal, khi i> minVal, cập nhật (giảm i đi 1), thực hiện -
      • nếu tôi
      • Thoát khỏi vòng lặp
    • nếu x mod i giống 0, thì -
      • return x mod 1337

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

3

Đầu ra

123