Нужна лучшая логика при поиске количества чисел палиндрома в диапазоне

Question

У меня есть два числа: A = 10 и B = 20.

Теперь мне нужно подсчитать число палиндром в диапазоне (A, B)

Я попытался это:

s = list(map(int,raw_input().split())) 
a = s[0] 
b = s[1] 

l = range(s[0],s[1]+1) 
# print "list : ",l 

def isNumberPalindrome(n): 
    return str(n) == str(n)[::-1] 

x = filter(isNumberPalindrome, l) 
# print " All Palindorme numbers : ",x 
count = len(x) 
print count 

У меня есть проблему памяти, превышающей, если А и В в диапазон 10^18.

Может кто-нибудь предложить мне, как это решить.

Заранее спасибо

Answer 1

Используйте генератор вместо вызова диапазона().

from __future__ import print_function 

def isNumberPalindrome(n): 
    return str(n) == str(n)[::-1] 

a = pow(10, 18) 
b = pow(10, 19) + 1 

def gen_range(start, end): 
    i = long(start) 
    while i < end: 
     yield i 
     i = i + 1 

count = 0 
for l in gen_range(a, b): 
    count += isNumberPalindrome(l) 

print(count) 

Answer 2

Это не совсем ответ. Но учтите следующее:

Для диапазона 10^n до 10^n+1 вы можете найти количество палиндромов в постоянное время. Это 10^ceil(n/2) - 10^ceil(n/2)-1. Потому что (например) для n = 6 и диапазон от 10^6 до 10^7 (1 000 000 - 10 000 000). Количество палиндромов является числом возможных чисел от 1000 до 10000 (которые представляют собой первую половину исходных чисел 4315 это первая половина 4315134 и так на).

Таким образом, вы не фильтруете числа, а находите, сколько палиндромов вы можете генерировать в таком диапазоне.