Подсчет количества натуральных чисел, которые лексикографически меньше определенного числа. ⇐ Python

[Anonymous]

Предположим, у меня есть число num, и я хочу посчитать количество положительных целых чисел в диапазоне [1, n], которые лексикографически меньше, чем num и n — произвольное большое целое число. Число x лексикографически меньше числа y, если преобразованная строка str(x) лексикографически меньше преобразованной строки str(y). Я хочу сделать это эффективно, поскольку n может быть большим (например, 10^9). Моя идея заключается в использовании цифрового динамического программирования.
По сути, я думаю, что каждое число в диапазоне [1,n] может быть представлено как строка len(str(n)) slots. В каждом слоте верхней границей для этого является либо цифра в последней позиции num (это для случая, когда мы выбираем конечные нули), либо цифра в последней позиции n. Это связано с тем, что если предыдущая цифра уже меньше соответствующей цифры в num, то мы можем выбрать любую цифру до соответствующей цифры в n. Ниже приведен мой код на Python, который пытается это сделать

Код: Выделить всё

from functools import cache

def count(num, n):
num = str(num)
n = str(n)
max_length = len(n)
@cache
def dp(indx, compare_indx, tight, has_number):
if indx == max_length:
return int(has_number)
ans = 0
upper_bound = int(num[compare_indx]) if tight else int(n[indx])
for digit in range(upper_bound + 1):
if digit == 0 and not has_number:
ans += dp(indx + 1, compare_indx, tight and (digit == upper_bound), False)
else:
ans += dp(indx + 1, min(compare_indx + 1, len(num) - 1), tight and (digit == upper_bound), True)
return ans
return dp(0, 0, True, False)

Однако count(7, 13) выводит 35, что неверно, поскольку лексикографический порядок [1, 13] равен [1, 10, 11 , 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], поэтому count(7, 13) должно быть 10. Может ли кто-нибудь мне помочь?

Подробнее здесь: https://stackoverflow.com/questions/790 ... aller-than