I use python and get about 1000ms...
But I see there are a of submissions within 100ms. Could anyone share their codes within 100ms?
I used the following approach. Let's denote the biggest palindrome product as
palindrome = M * L. For N > 1 this palidrome has even number of digits and it can be represented as the sum:
palindrome = upper * 10^N + lower
We can expect that M and L are close to 10^N and we can represent them as
M = 10^N - i,
L = 10^N - j and hence
palindrome = (10^N - i) * (10^N - j) = 10^N * (10^N - (i + j)) + i * j
If we assume that i * j < 10^N (this assumption turned out to be true for N > 1) we can represent upper and lower in the following way:
upper = 10^N - (i + j)
lower = i * j
This is the system of equations which can be solved if we know upper and lower. Let's denote sum of i and j as
a = i + j. It can be calculated as
a = 10^N - upper. Because
j = a - i equation for lower can be rewritten as
lower = a * i - i * i
This is a quadratic equation which can be solved using standard methods from textbooks.
Here is the algorithm:
if n == 1: return 9 for a in xrange(2, 9 * 10**(n-1)): upper = 10**n - a lower = reverseNumber(upper) # solve the equation # lower == a * i - i * i # if it has whole number solution then # return (10**n - i) * (10**n - j) % 1337
This solution is under 100ms but it is still slower than 40% of solutions. So there might be a better approach.
why upper bound of a is 9 * 10**(n-1) rather than 18* 10**(n-1)
a > 9 * 10**(n-1) then
upper = 10**n - a will have less than n digits. This approach won't work in this case.
For N > 1 this palidrome has even number of digits
I understand for even N there's direct solution, but I don't see the existence proof of the even number of digits for every N>1? any trivial proof?
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.