title: Count of numbers between A and B (inclusive) that have sum of digits equal to S
body: <p>The problems is to find the count of numbers between A and B (inclusive) that have sum of digits equal to S.</p>
  
  <p>Also print the smallest such number between A and B (inclusive).</p>
  
  <p>Input:</p>
  
  <p>Single line consisting of A,B,S.</p>
  
  <p>Output:</p>
  
  <p>Two lines.</p>
  
  <p>In first line the number of integers between A and B having sum of digits equal to S.</p>
  
  <p>In second line the smallest such number between A and B.</p>
  
  <p>Constraints:</p>
  
  <p>1 &lt;= A &lt;= B &lt; 10^15</p>
  
  <p>1 &lt;= S &lt;= 135</p>
  
  <p>Source: <a href="http://www.hackerearth.com/problem/algorithm/sum-of-digits-8/" rel="nofollow">Hacker Earth</a></p>
  
  <p>My solution works for only 30 pc of their inputs. What could be the best possible solution to this?</p>
  
  <p>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:</p>
  
  <pre><code>def sum(n):
      if (n&lt;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&lt;=b :        
  if (a % 10 == 0 ):
      su = sum(a)
      print a 
  if ( s == su):
      count+=1
      if (a&lt;= min):
          min=a 
  a+=1
  su+=1
  print count 
  print min 
  </code></pre>