2
\$\begingroup\$

I want to find the lowest hop count from source to destination. The challenge, in summary:

The first line contains the number of test cases T, 1 ≤ T ≤ 100000.
The next T lines each contains three integers A, B, and M. 1 ≤ A ≤ B ≤ 1012. 1 ≤ M ≤ 1012.

For each test case, print the number of multiples of M that are in the range [A, B] (inclusive).

My output is correct but the execution time of my program is like 1.0015 seconds when given 100000 entries. But I need to do the program within 1 second time frame. I have tried a lot to reduce the execution time but couldn't. Can anybody help me to achieve an execution time within 1 sec.

#include<stdio.h>
int main()
{
    unsigned int n, i, j, k, h,count=0,l=0;
    scanf("%u", &n);
    for (i=0;i<n;i++)
    {
        scanf("%u %u %u", &j, &k, &h);
        l=j;
        count = 0;
        while(l<=k)
        {
          if(l%h==0)
          {
            count=count+1;
          }
          l++;
        }
        printf("%u\n", count);
    }
    return 0;
}

sample input-> 1 10 2

sample output-> 5

\$\endgroup\$
1
\$\begingroup\$

Data declarations

Your data types are not large enough. By the C standard, an int is only guaranteed to hold up to 32767, which is smaller than 100000. Similarly, an int could be insufficient to hold the values of A, B, and M. You'll need a long long or int64_t.

A big block of declarations like this is not ideal:

unsigned int n, i, j, k, h,count=0,l=0;
  • You should declare variables as close to the point of use and in as tight a scope as possible.
  • Single-character names are cryptic.

Algorithm

You don't have to simulate a kangaroo, counting hops, to answer these questions. The answer will be roughly

$$\frac{B - A}{M}$$

… except that you have to take care of fencepost (off-by-one) errors at the edges. I'll leave it to you to figure out the details.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.