Time Limit Exceeds [HS11DIVS] - How to make it faster?

Here is the question. From SPOJ [HS11DIVS]. Now , the problem is that my code works perfectly for small numbers. But when it comes to Large numbers , the time limit exceeds.

I am not getting any hint on how to make it more efficient. The code is simple enough to understand. I mean its a pretty basic question but difficult to make it efficient.


For given integers a and b we need to find how many integers in the range [a,b] are divisible by a number x, and have the additional property that the sum of their digits lies in the ,range [l,r] for given l,r.


Input


In the first line you're given a and b ( 1 <= a <= b < 10^100 ). In
the second line you're given three positive integers x ( 1 <= x <= 10
), l, r ( 1 <= l <= r <= 1,000 ).


Output


In the first and only line output the result modulo 1,000,000,007.

And this is my attempt to the question.

UPDATED :

#include 

int sumOfDigits(int number)
{
  int sum=0;
  while(number!=0)
  {
     sum = sum + (number%10);
     number = number/10;
  }
  return sum;
}

/* UPDATED SEGMENT */

unsigned long long int first(unsigned long long int a,unsigned long long int b,int x)
{
  unsigned long long int m = a%x;
      a = a - m + x;
      return a;
} 

int main (void)
{
  unsigned long long int a, b; 
  int x, l, r;
  int counter=0,sum;
  scanf("%llu %llu", &a, &b);
  scanf("%d %d %d", &x, &l, &r);
  a = first(a,b,x);   // gives the first number divisible by x.
  while(a=sum) // check if sum of digits lies b/w l&r.
    {
        counter+=1;
    }
    a+=x;     // increment a by multiples of x.
  }
  printf("%d", counter);
  return 0;
}

Where am i being inefficient? I even calculated the first number divisible by x , and then assign it to a , and then increase a by multiples of x ( a+=x; ).

Here is a sample output :


Input:
1 100 5 10 50


Output: 5

First you need to correct first()

unsigned long long int first(unsigned long long int a,unsigned long long int b,int x)
{
  // Removed b
  return a;
}       ^^^ otherwise the main loop will run through everything in the main loop (from 0).

Though first() looks efficient because you are doing it only once. The questioner may carefully craft a,b,x to take a long time. So you can optimize its evaluation:

unsigned long long int m = a%x;
a = a - m + x;  // a now first valid value.

Your summing of the digits does a lot of extra work.

99   = 18
199  = 19 1 + sum_of_digits(99)

You can use this to cache results and re-use them in later calculations.

Pre compute the following array and compile it into your application.

sum_cache[10000]   cache  = {
               /* Generated code goes here */

                            };

int sumOfDigits(int number)
{
     int sum=sum_cache[number % 10000];
     for(number = number/10000;number != 0; number/= 10)
     {
         sum    += (number%10);
     }
     return sum;
}

Edit (based on comments below)

int sumOfDigits(int number)
{
  int sum=0;
  while(number!=0)
  {
     sum = sum + (number%10);
     number = number/10;
  }
  return sum;
}
int main()
{
    std::ofstream data("data.d");

    data << 0;
    for(int loop=1; loop < 10000; ++loop)
    {
        data << ", " << sumOfDigits(loop);
    }
}

Then change the code above too:

sum_cache[]   cache  = {
               /* Generated code goes here */
 #include "data.d"
                       };

Edit 2:

Improved: (I was hopping you would see the simple optimization)

Does this help?

int sumOfDigits(int number)
{
     int sum=0;
     for(;number != 0; number/= 10000)
     {
         sum    += sum_cache[number % 10000];
     }
     return sum;
}

Max Loop:

Original Version (your Code)       100      = 100
First Cache Version                100-4    = 96
Second Cache Version               100/4    = 25

StackExchange Code Review Q#5064, answer score: 4