Counting the number of positive integers that are lexicographically smaller than a specific number

Hello everyone! I hope this video has helped solve your questions and issues. This video is shared because a solution has been found for the question/problem. I create videos for questions that have solutions. If you have any other issues, feel free to reach out to me on Instagram:   / ky.emrah  

Below, you can find the text related to the question/problem. In the video, the question will be presented first, followed by the answers. If the video moves too fast, feel free to pause and review the answers. If you need more detailed information, you can find the necessary sources and links at the bottom of this description. I hope this video has been helpful, and even if it doesn't directly solve your problem, it will guide you to the source of the solution. I'd appreciate it if you like the video and subscribe to my channel!Counting the number of positive integers that are lexicographically smaller than a specific number

Say I have a number num and I want to count the number of positive integers in the range [1, n] which are lexicographically smaller than num and n is some arbitrary large integer. A number x is lexicographically smaller than a number y if the converted string str(x) is lexicographically smaller than the converted string str(y). I want to do this efficiently since n could be large (eg. 10^9). My idea for this is using digit dynamic programming.
num
[1, n]
num
n
x
y
str(x)
str(y)
n
10^9
Essentially what I'm thinking is that every number in the range [1,n] can be represented as a string of len(str(n)) slots. At each slot, the upper bound for this is either the digit at the last position of num (this is for the case where we pick trailing zeros) or the digit at the last position of n. This is because if the previous digit is already smaller than the corresponding digit in num then we are free to pick any digit up to the corresponding digit in n. Below is my code in Python that attempts to do this
[1,n]
len(str(n))
num
n
num
n
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)

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)

However, count(7, 13) outputs 35 which is not correct since the lexicographical order of [1, 13] is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9] so count(7, 13) should be 10. Can anyone help me out here?
count(7, 13)
[1, 13]
count(7, 13)
10


Tags: python,algorithm,dynamic-programmingSource of the question:
https://stackoverflow.com/questions/7...

Question and source license information:
https://meta.stackexchange.com/help/l...
https://stackoverflow.com/