Найти самый большой палиндром из произведения двух n-значных чисел - python

Question

Я решаю эту проблему, и описание выглядит так:

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

Мое текущее решение работает, только если значение n равно 4 или меньше.Я пытался изменить его, но, похоже, мне нужна помощь в выяснении этого.Как мне решить это за меньшее время?Это мой код:

class Solution:
    def largestPalindrome(self, n):
        """
        :type n: int
        :rtype: int
        """
        if (n == 1):  #it returns '9' if the input is a single digit number
            return 9
        highest = 0
        high = '9'  
        low = '1'
        for k in range(2,n+1):
            high = high + '9' #increase the number of digits until 'n' is reached
            low = low + '0'  
            for i in range(int(low), int(high)-1): 
                for j in range(int(low) + 1, int(high)):
                    num = str(i * j)
                    if (int(num) > highest and num == num[::-1]):  # if it is a palindrome and highest then 
                        highest = int(num)  # highest  is the new number
        return highest % 1337

Answer 1

Вы могли бы значительно ускорить это, избавившись от ненужных дел.Для начала:

• Поскольку порядок двух целых чисел не имеет значения, вам нужно только рассмотреть случаи, когда j> = i, поэтому вы можете установить нижнюю границу для вашего j-цикла вJ = я.(Или, возможно, выше; см. Ниже.)
• Поскольку вы ищете САМЫЙ БОЛЬШОЙ палиндром, вы можете сэкономить много времени, зацикливая i и j от самых высоких до самых низких значений вместо самых низких и самых высоких.Для каждого i вы можете остановить j-цикл, как только найдете первый (самый высокий) j, который дает i * j = палиндром, потому что любое меньшее значение j даст меньший палиндром.
• Вы можетеиспользуйте свой самый высокий палиндром, чтобы установить более разумные нижние границы для j.Нет смысла проверять любые j-значения, меньшие, чем самый высокий / i, потому что даже если они дают вам палиндром, это будет меньше, чем у вас уже есть.

Другой подход: вместоцикл по i и j, цикл по возможным палиндромам.Начните с максимально возможного палиндрома с 2n цифрами и проверьте, можно ли выразить его как произведение двух n-значных чисел;если вы осторожны с границами, которые вы устанавливаете для возможных факторов, это не должно требовать проверки многих случаев.Если, если можно выразить как продукт, все готово;если нет, попробуйте следующий палиндром и повторяйте, пока не найдете то, что работает.