Indeed, there is an approach to this scheme, which, as it turned out, works quite often. It can also be used to enumerate all X with this property, provided that their number is quite small. You can even use it to aggregate some associative operator across X with a given property, for example, to find their sum.
To understand the general idea, we will try to formulate the condition X ≤ Y in terms of decimal representations of X and Y.
Say we have X = x 1 x 2 ... x n - 1 x n and Y = y 1 y 2 ... y n - 1 y n , where x i and y i are the decimal digits of X and Y. If the numbers have different lengths, we can always add zero digits to the beginning of the shorter one.
We define leftmost_lo as the smallest self with x i <y <sub> javascript>. Define leftmost_lo as n + 1, if I do not exist. Similarly, we define leftmost_hi as the smallest i with x i > y i , or n + 1 otherwise.
Now X ≤ Y is true, if it is, if leftmost_lo <= leftmost_hi . With this observation, it becomes possible to apply a dynamic programming approach to a problem that “sets” the numbers X one after another. I will demonstrate this with your problem examples:
Compute the number f (Y) of the integers X with the property X ≤ Y and X has the digit sum 60
Let n be the number of Y-digits, and y[i] i-th decimal digit Y in accordance with the above definition. The following recursive algorithm solves the problem:
count(i, sum_so_far, leftmost_lo, leftmost_hi): if i == n + 1: # base case of the recursion, we have recursed beyond the last digit # now we check whether the number X we built is a valid solution if sum_so_far == 60 and leftmost_lo <= leftmost_hi: return 1 else: return 0 result = 0 # we need to decide which digit to use for x[i] for d := 0 to 9 leftmost_lo' = leftmost_lo leftmost_hi' = leftmost_hi if d < y[i] and i < leftmost_lo': leftmost_lo' = i if d > y[i] and i < leftmost_hi': leftmost_hi' = i result += count(i + 1, sum_so_far + d, leftmost_lo', leftmost_hi') return result
Now we have f(Y) = count(1, 0, n + 1, n + 1) , and we solved the problem. We can add memoization function to make it fast. The runtime is O (n 4 ) for this particular implementation. In fact, we can skillfully optimize an idea to make it O (n). This remains as an exercise for the reader (Hint: you can compress the information stored in leftmost_lo and leftmost_hi into one bit, and you can trim if sum_so_far > 60 ). A solution can be found at the end of this post.
If you look closely, sum_so_far is just an example of an arbitrary function that calculates a value from a digital sequence X. It can be any function that can be calculated by a number from a number and outputs a fairly small result. It can be a product of numbers, a bitmask of a set of numbers that fulfill a specific property, or much more.
It can also be just a function that returns 1 or 0, depending on whether the number contains only the numbers 4 and 7, which allows the second example to be trivial. We have to be a little careful because we are allowed to have leading zeros at the beginning, so we need to carry an extra bit through recursive function calls telling us whether we are allowed to use zero as a digit.
Compute the number f (Y) of integers X with the property X ≤ Y and X is palindromic
This is a little tougher. We need to be careful with leading zeros: the mirror point of a palindromic number depends on how many leading zeros we have, so we will need to track the number of leading zeros.
There are several ways to simplify this: if we can calculate f (Y) with an additional restriction so that all numbers X must have the same digits, such as Y, then we can also solve the original problem by repeating all possible digits and adding the results.
So we can just assume that we have no leading zeros:
count(i, leftmost_lo, leftmost_hi): if i == ceil(n/2) + 1: # we stop after we have placed one half of the number if leftmost_lo <= leftmost_hi: return 1 else: return 0 result = 0 start = (i == 1) ? 1 : 0 # no leading zero, remember? for d := start to 9 leftmost_lo' = leftmost_lo leftmost_hi' = leftmost_hi # digit n - i + 1 is the mirrored place of index i, so we place both at # the same time here if d < y[i] and i < leftmost_lo': leftmost_lo' = i if d < y[n-i+1] and n-i+1 < leftmost_lo': leftmost_lo' = n-i+1 if d > y[i] and i < leftmost_hi': leftmost_hi' = i if d > y[n-i+1] and n-i+1 < leftmost_hi': leftmost_hi' = n-i+1 result += count(i + 1, leftmost_lo', leftmost_hi') return result
The result will again be f(Y) = count(1, n + 1, n + 1) .
UPDATE:. If we want to not only count the numbers, but, perhaps, enumerate them or calculate from them some aggregate function that does not reveal the structure of the group, we need to ensure that the lower bound of X is also observed during the recursion. This adds a few more options.
UPDATE 2: O (n) Solution for the example “sum of digit 60”:
In this application, we put the numbers from left to right. Since we are only interested in whether the value is leftmost_lo < leftmost_hi , we add a new parameter lo . lo true leftmost_lo < i and false otherwise. If lo true, we can use any digit for position i . If this is a lie, we can use the digits 0 only for Y [i], since any larger digit calls leftmost_hi = i < leftmost_lo and therefore cannot lead to a solution. The code:
def f(i, sum_so_far, lo): if i == n + 1: return sum_so_far == 60 if sum_so_far > 60: return 0 res = 0 for d := 0 to (lo ? 9 : y[i]): res += f(i + 1, sum + d, lo || d < y[i]) return res
Perhaps this way of looking at it is somewhat simpler, but also a little less explicit than the leftmost_lo / leftmost_hi . It also does not work immediately for several more complex scenarios, such as the palindrome problem (although it can also be used there).