Count of numbers between A and B (inclusive) that have sum of digits equal to S

Question

The problems is to find the count of numbers between A and B (inclusive) that have sum of digits equal to S.

Also print the smallest such number between A and B (inclusive).

Input:

Single line consisting of A,B,S.

Output:

Two lines.

In first line the number of integers between A and B having sum of digits equal to S.

In second line the smallest such number between A and B.

Constraints:

1 <= A <= B < 10^15

1 <= S <= 135

Source: Hacker Earth

My solution works for only 30 pc of their inputs. What could be the best possible solution to this?

The algorithm I am using now computes the sum of the smallest digit and then upon every change of the tens digit computes the sum again. Below is the solution in Python:

def sum(n):
    if (n<10):return n
    return n%10 + sum(n/10)

stri = raw_input()

min = 99999
stri = stri.split(" ")

a= long  (stri[0])
b= long  (stri[1])
s= long  (stri[2])

count= 0
su = sum(a)

while a<=b :        
if (a % 10 == 0 ):
    su = sum(a)
    print a 
if ( s == su):
    count+=1
    if (a<= min):
        min=a 
a+=1
su+=1
print count 
print min 

Answer 1

There are two separate problems here: finding the smallest number between those numbers that has the right digit sum and finding the number of values in the range with that digit sum. I'll talk about those problems separately.

Counting values between A and B with digit sum S.

The general approach for solving this problem will be the following:

• Compute the number of values less than or equal to A - 1 with digit sum S.
• Compute the number of values less than or equal to B with digit sum S.
• Subtract the first number from the second.

To do this, we should be able to use a dynamic programming approach. We're going to try to answer queries of the following form:

How many D-digit numbers are there, whose first digit is k, whose digits that sum up to S?

We'll create a table N[D, k, S] to hold these values. We know that D is going to be at most 16 and that S is going to be at most 136, so this table will have only 10 × 16 × 136 = 21,760 entries, which isn't too bad. To fill it in, we can use the following base cases:

• N[1, S, S] = 1 for 0 ≤ S ≤ 9, since there's only one one-digit number that sums up to any value less than ten.
• N[1, k, S] = 0 for 0 ≤ S ≤ 9 if k ≠ S, since no one-digit number whose first digit isn't a particular sum sums up to some value.
• N[1, k, S] = 0 for 10 ≤ S ≤ 135, since no one-digit number sums up to exactly S for any k greater than a single digit.
• N[1, k, S] = 0 for any S < 0.

Then, we can use the following logic to fill in the other table entries:

• N[D + 1, k, S] = sum(i from 0 to 9) N[D, i, S - k].

This says that the number of (D+1)-digit numbers whose first digit is k that sum up to S is given by the number of D-digit numbers that sum up to S - k. The number of D-digit numbers that sum up to S - k is given by the number of D-digit numbers that sum up to S - k whose first digit is 0, 1, 2, ..., 9, so we have to sum up over them.

Filling in this DP table takes time only O(1), and in fact you could conceivably precompute it and hardcode it into the program if you were really concerned about time.

So how can we use this table? Well, suppose we want to know how many numbers that sum up to S are less than or equal to some number X. To do this, we can process the digits of X one at a time. Let's write X one digit at a time as d₁ ... d_n. We can start off by looking at N[n, d₁, S]. This gives us the number of n-digit numbers whose first digit is d₁ that sum up to S. This may overestimate the number of values less than or equal to X that sum up to S. For example, if our number is 21,111 and we want the number of values that sum up to exactly 12, then looking up this table value will give us false positives for numbers like 29,100 that start with a 2 and are five digits long, but which are still greater than X. To handle this, we can move to the next digit of the number X. Since the first digit was a 2, the rest of the digits in the number must sum up to 10. Moreover, since the next digit of X (21,111) is a 1, we can now subtract from our total the number of 4-digit numbers starting with 2, 3, 4, 5, ..., 9 that add up to 10. We can then repeat this process one digit at a time.

More generally, our algorithm will be as follows. Let X be our number and S the target sum. Write X = d₁d₂...d_n and compute the following:

# Begin by starting with all numbers whose first digit is less than d[1].
# Those count as well.
result = 0
for i from 0 to d[1]:
    result += N[n, i, S]

# Now, exclude everything whose first digit is d[1] that is too large.
S -= d[1]
for i = 2 to n:
    for j = d[i] to 8:
        result -= N[n, d[i], S]
    S -= d[i]

The value of result will then be the number of values less than or equal to X that sum up to exactly S. This algorithm will only run for at most 16 iterations, so it should be very quick. Moreover, using this algorithm and the earlier subtraction trick, we can use it to compute how many values between A and B sum up to exactly S.

Finding the smallest value in [A, B] with digit sum S.

We can use a similar trick with our DP table to find the smallest number greater than A number that sums up to exactly S. I'll leave the details as an exercise, but as a hint, work one digit at a time, trying to find the smallest number for which the DP table returns a nonzero value.

Hope this helps!