Could any python experts share their codes within 100ms?


  • 0
    Z

    I use python and get about 1000ms...
    But I see there are a of submissions within 100ms. Could anyone share their codes within 100ms?

    Thanks!


  • 2
    N

    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.


  • 0
    X

    @nizametdinov said in Could any python experts share their codes within 100ms?:

    why upper bound of a is 9 * 10**(n-1) rather than 18* 10**(n-1)


  • 0
    N

    @xiaoyudeng666, if a > 9 * 10**(n-1) then upper = 10**n - a will have less than n digits. This approach won't work in this case.


  • 0
    J

    @nizametdinov said in Could any python experts share their codes within 100ms?:

    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?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.