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