Question

479. Largest Palindrome Product

中文文档

Description

Given an integer n, return _the largest palindromic integer that can be represented as the product of two n-digits integers_. Since the answer can be very large, return it modulo 1337.

 

Example 1:

Input: n = 2
Output: 987
Explanation: 99 x 91 = 9009, 9009 % 1337 = 987

Example 2:

Input: n = 1
Output: 9

 

Constraints:

• 1 <= n <= 8

Solutions

Solution 1

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
}