Возвращает наибольшее n такое, что R [n] = S

Question

Напишите ответ функции (str_S), который, учитывая строку base-10 , представляет собой целое число S, возвращает наибольшее n такое, что R (n) = S. Вернуть ответ в виде строки в представлении base-10. Если там нет такого n, верните «None». S будет положительным целым числом, не большим , чем 10^25.

где R (п) число zombits во время п:

R(0) = 1 
R(1) = 1 
R(2) = 2 
R(2n) = R(n) + R(n + 1) + n (for n > 1) 
R(2n + 1) = R(n - 1) + R(n) + 1 (for n >= 1) 

Test cases 
========== 

Inputs: 
    (string) str_S = "7" 
Output: 
    (string) "4" 

Inputs: 
    (string) str_S = "100" 
Output: 
    (string) "None" 

Моя программа ниже является правильным, но это не является масштабируемым, поскольку здесь диапазон S может быть очень большое количество, как 10^24. Может ли кто-нибудь помочь мне с некоторым предложением улучшить код дальше, чтобы он мог охватывать любой случай ввода.

def answer(str_S): 

    d = {0: 1, 1: 1, 2: 2} 
    str_S = int(str_S) 
    i = 1 
    while True: 

     if i > 1: 
      d[i*2] = d[i] + d[i+1] + i 
      if d[i*2] == str_S: 
       return i*2 
      elif d[i*2] > str_S: 
       return None 

     if i>=1: 
      d[i*2+1] = d[i-1] + d[i] + 1 
      if d[i*2+1] == str_S: 
       return i*2 + 1 
      elif d[i*2+1] > str_S: 
       return None 

     i += 1 

print answer('7') 

Answer 1

Прежде всего, где у вас проблемы с масштабированием? Я запустил ваш код на 30-значный номер, и, похоже, все в порядке. У вас есть ограничение на память? Python обрабатывает произвольно большие целые числа, хотя очень большие передаются в цифровой арифметический режим.

Учитывая плотность значений R, я подозреваю, что вы можете сэкономить место и время, если вы переключитесь на прямой массив: используйте значение как индекс массива вместо ключа dict.