# 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 <stdio.h>

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<=b)
{
sum = sumOfDigits(a);
if(l<=sum && r>=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

• Would you please avoid making changes to the code in the question after the question has been asked? I see in the edit history that you have altered the code repeatedly. This will invalidate any answers already given and is generally not approved of at CR. Aug 18, 2014 at 12:01

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

• I didnt get the sum_cache part. What is this " Generated code goes here " ? Which code shall i place there? Sep 29, 2011 at 20:30
• You should write a program that generates the pre-computed values for 1->100000 and outputs them as a comma separated list. Then you add the output (the comma separated list of values) into this code. Sep 29, 2011 at 20:36
• But the thing is , i can't create another file and use it. I have to do everything in 1 program only. here is the link to the problem : hs.spoj.pl/problems/HS11DIVS Sep 29, 2011 at 20:48
• 1 program != 1 file. A single program can be compiled from n files. Sep 29, 2011 at 22:12
• @Niteesh Mehra: Once you have generated the numbers and placed the output in a file you can throw the first program away. Using a program is just a short cut to typing out the number by hand (you can type all the numbers by hand and get the same result there is only 10000 in my version but I can see you doing the first 1 million easily). Sep 29, 2011 at 23:08