使用 C++ 找出最大的回文乘积

假设我们有输入 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
  • 返回 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

更新时间： 01-Jun-2020

111 浏览次数

开启你的 事业

完成课程后获得认证

开始
广告