patterncMinor
HackerEarth Crazy kangaroo challenge
Viewed 0 times
kangaroocrazyhackerearthchallenge
Problem
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.
sample input-> 1 10 2
sample output-> 5
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
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
Solution
Data declarations
Your data types are not large enough. By the C standard, an
A big block of declarations like this is not ideal:
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.
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.
Code Snippets
unsigned int n, i, j, k, h,count=0,l=0;Context
StackExchange Code Review Q#80578, answer score: 4
Revisions (0)
No revisions yet.