Find all variations of a digit sum

Question

Can anyone please direct me to an algorithm/formulae that says how to calculate all variations of a digit sum with a certain upper limit

So for example, if my digit sum is 6 and the upper limit is 123, then all variations for that digit sum would be: 6, 15, 24, 33, 42, 51, 60, 105, 114 and 123.

The upper limit can be up to 10**18 and program needs to work in under 1 second(in C/CPP), so brute force is not an option.

Answer 1

I think there is a recursive approach to solve this problem: consider a procedure int f(bool limit, int bit_count, int bit_sum), which calculates the number of variations that are no longer than bit_count bits that have a bit sum of bit_sum. The bool parameter limit denotes whether the limit (in your example, 123) takes effect.

Suppose Limit[i] denotes the i-th bit of the limit.

int f(bool limit, int bit_count, int bit_sum){
    if(bit_sum < 0)
        return 0;
    if(bit_count == -1)
        if(bit_sum == 0)
            return 1;
        else
            return 0;

    int ans = 0;
    for(int i = 0; i <= limit ? Limit[bit_count] : 9; i++){
        ans += f(limit && i == Limit[bit_count], bit_count - 1, bit_sum - i);
    }
    return ans;
}

In your example of bit sum as 6 and upper limit as 123, Limit[2] = 1, Limit[1] = 2, Limit[0] = 3. The answer is f(true, 2, 6).

For the sake of quick, you can convert this recursive approach into a dynamic programming approach by a record table. The time complexity of the corresponding DP approach is O(bit_sum * log(upper_limit)). I think this speed can meet your 1 second requirement.

Answer 2

Create a DP based solution to calculate sum of at most k digits that sum to n.

F(k,n) = sum_i F(k-1, n-i)

Assume your max has k digits and the most significant digit is sig(max) and dropsig(max) is the number without the most significant digit.

G(k,max,n) = F(k-1, n)+ G(k-1, dropsig(max), n-sig(max) ) + sum_i (k-1, n-i) for i = 1 to sig(max) -1 .

Obviously, you have to take care of corner cases. But here is the summary.

The first component corresponds to cases where the length of the numbers are less than the length of maximum number.

The second component corresponds to cases where the most significant digit of solution is same as the maximum significant digit of the max.

The third component corresponds to cases where most significant digit of the solution is less than significant digit of the max, but greater than or equal to 1.