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.
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
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?
I couldn't follow the logic in your explanation, but this shouldn't need dynamic programming.
In essence you want to do a separate count for each possible width of an integer. For instance, when calling count(7, 13), you'd want to count:
The outcome is the sum: 6 + 4 = 10
Take count(86, 130) as another example, where the first argument has more than one digit:
Total is: 115
So some care has to be taken at the high-end of the ranges: when it is a proper prefix of the first argument, it should be included, if not, it should be excluded. And of course, for that last group (with the greatest number of digits) you should take care not to exceed the value of the second argument.
Here is how you could code that logic:
def count(num, n):
strnum = str(num)
lennum = len(strnum)
max_length = len(str(n))
strnum += "0" * (max_length - lennum) # pad with zeroes at the right
count = 0
low = 1
for width in range(1, max_length + 1):
high = int(strnum[:width])
addone = width < lennum and n >= high
count += min(high, n + 1) - low + addone
low *= 10
return count