Question

479. 最大回文数乘积

English Version

题目描述

给定一个整数 n ，返回 _可表示为两个 n 位整数乘积的 最大回文整数_ 。因为答案可能非常大，所以返回它对 1337 取余 。

 

示例 1:

输入：n = 2
输出：987
解释：99 x 91 = 9009, 9009 % 1337 = 987

示例 2:

输入： n = 1
输出： 9

 

提示:

• 1 <= n <= 8

解法

方法一

class Solution:
  def largestPalindrome(self, n: int) -> int:
    mx = 10**n - 1
    for a in range(mx, mx // 10, -1):
      b = x = a
      while b:
        x = x * 10 + b % 10
        b //= 10
      t = mx
      while t * t >= x:
        if x % t == 0:
          return x % 1337
        t -= 1
    return 9

class Solution {
  public int largestPalindrome(int n) {
    int mx = (int) Math.pow(10, n) - 1;
    for (int a = mx; a > mx / 10; --a) {
      int b = a;
      long x = a;
      while (b != 0) {
        x = x * 10 + b % 10;
        b /= 10;
      }
      for (long t = mx; t * t >= x; --t) {
        if (x % t == 0) {
          return (int) (x % 1337);
        }
      }
    }
    return 9;
  }
}

class Solution {
public:
  int largestPalindrome(int n) {
    int mx = pow(10, n) - 1;
    for (int a = mx; a > mx / 10; --a) {
      int b = a;
      long x = a;
      while (b) {
        x = x * 10 + b % 10;
        b /= 10;
      }
      for (long t = mx; t * t >= x; --t)
        if (x % t == 0)
          return x % 1337;
    }
    return 9;
  }
};

func largestPalindrome(n int) int {
  mx := int(math.Pow10(n)) - 1
  for a := mx; a > mx/10; a-- {
    x := a
    for b := a; b != 0; b /= 10 {
      x = x*10 + b%10
    }
    for t := mx; t*t >= x; t-- {
      if x%t == 0 {
        return x % 1337
      }
    }
  }
  return 9
}