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

Question

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

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

Input:

A single line consisting of A, B, S.

Output:

Two lines.

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

The second line contains the smallest such number between A and B.

Limitations:

1 <= A <= B <10 ^ 15

1 <= S <= 135

Source: Hacker Earth

My solution only works on 30 pcs. their inputs. What could be the best solution?

The algorithm I use calculates the sum of the smallest digit, and then with each change of dozens of digits, the sum is calculated again. The following 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

: , , . .

A B S.

:

• , A - 1, sum S.
• , B sum S.
• .

. :

D- , k, S?

N [D, k, S], . , D 16 S 136, 10 ; 16 ; 136 = 21 760 , . , :

• N [1, S, S] = 1 0 & le; S & le; 9, , .
• N [1, k, S] = 0 0 & le; S & le; 9, k & ne; S, , , .
• N [1, k, S] = 0 10 & le; S & le; 135, S k, .
• N [1, k, S] = 0 S < 0.

:

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

, (D + 1) - , k, S, D- , S-k. D- , S-k, D- , S-k, 0, 1, 2,..., 9, .

DP O (1), , .

, ? , , , , S, X. X . X , d ₁... d _n. N [n, d ₁, S]. n- , d ₁, S. , X, S. , 21111, , 12, , 29 100, 2 , X. , X. 2, 10. , X (21,111) 1, 4- , 2, 3, 4, 5,..., 9, 10. .

. X - , S - . X = d ₁ d ₂... d _n :

# 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]

result , X, S. 16 , . , , S.

[A, B] sum S.

DP, , , A, S. , , , DP .

, !