Problem
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
Solution (Java)
class Solution {
public int largestPalindrome(int n) {
long pow10 = (long) Math.pow(10, n);
long max = (pow10 - 1) * (pow10 - (long) Math.sqrt(pow10) + 1);
long left = (max / pow10);
long t = pow10 / 11;
t -= ~t & 1;
for (long i = left; i > 0; i--) {
for (long j = t, num = gen(i); j >= i / 11; j -= 2) {
if (num % j == 0) {
return (int) (num % 1337);
}
}
}
return 9;
}
private long gen(long x) {
long r = x;
while (x > 0) {
r = r * 10 + x % 10;
x /= 10;
}
return r;
}
}
Solution (Python)
class Solution(object):
def largestPalindrome(self, n):
"""
:type n: int
:rtype: int
"""
if n == 1:
return 9
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
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).