Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/479.html

479. Largest Palindrome Product

Level

Hard

Description

Find the largest palindrome made from the product of two n-digit numbers.

Since the result could be very large, you should return the largest palindrome mod 1337.

Example:

Input: 2

Output: 987

Explanation: 99 x 91 = 9009, 9009 % 1337 = 987

Note:

The range of n is [1,8].

Solution

If n is 1, return 9. For n greater than 1, the maximum n-digit number is 10^n - 1. For each n-digit number, create a palindrome that has 2 * n digits and check whether there exists an n-digit number that is greater than or equal to the palindrome’s square root and can divide the palindrome completely. If such an n-digit number is found, return the palindrome mod 1337.

• Java
• C++
• Python
• Go

• class Solution {
      public int largestPalindrome(int n) {
          if (n == 1)
              return 9;
          long max = (long) Math.pow(10, n) - 1;
          long start = max - 1, end = max / 10 + 1;
          for (long i = max - 1; i >= end; i--) {
              String str = String.valueOf(i);
              StringBuffer sb = new StringBuffer(str).reverse();
              long palindrome = Long.parseLong(str + sb.toString());
              long min = (long) Math.ceil(Math.sqrt(palindrome));
              for (long j = max; j >= min; j--) {
                  if (palindrome % j == 0)
                      return (int) (palindrome % 1337);
              }
          }
          return -1;
      }
  }
  

• // OJ: https://leetcode.com/problems/largest-palindrome-product/
  // Time: O(10^N)
  // Space: O(1)
  class Solution {
  public:
      int largestPalindrome(int n) {
          if (n == 1) return 9;
          int mod = 1337, mx = pow(10, n) - 1, mn = pow(10, n - 1);
          auto valid = [&](long pal) {
              for (long div = mx; div * div >= pal; --div) {
                  if (pal % div == 0) return true;
              }
              return false;
          };
          for (int half = mx; half >= mn; --half) {
              long pal = half, tmp = half;
              for (; tmp; tmp /= 10) pal = pal * 10 + (tmp % 10);
              if (valid(pal)) return pal % mod;
          }
          return -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(object):
      def largestPalindrome(self, n):
          if n==1: return 9
          if n==2: return 987
          for a in xrange(2, 9*10**(n-1)):
              hi=(10**n)-a
              lo=int(str(hi)[::-1])
              if a**2-4*lo < 0: continue
              if (a**2-4*lo)**.5 == int((a**2-4*lo)**.5):
                  return (lo+10**n*(10**n-a))%1337
  

• 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
  }
  

All Problems

All Solutions