Nimmi Nimmi - 27 days ago 11
C Question

Hackerrank challenge timout

hey i am just trying to solve a challenge on hackerrank but in some test cases the code timeouts and i don't know why. This is the challenge.

And here is my code:

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main(){
int n, k, q;
scanf("%d %d %d",&n,&k,&q);
int qs[q];
int a[n];

for(int i = 0; i < n; i++){
scanf("%d", &a[i]);
}


for(int i = 0; i < q; i++){
scanf("%d",&qs[i]);
}

int lastNbr = a[n-1];
for(int i = 0; i < k; i++){
lastNbr = a[n-1];
for(int j = n - 1; j > -1; j--){
a[j] = (j-1 >= 0) ? a[j-1] : lastNbr;
}
}

for(int i = 0; i < q; i++){
printf("%d\n", a[qs[i]]);
}

return 0;
}

Answer

All right, lets start with analysing your algorithm's time complexity:

You have the 2 nested for loops which always go for n * k operations, as you rotate your array k times and you need n operations to make the rotation.

This goes as O(n * k), so it's about 10^10 operations on the worst case input, which is quite too much for this task.

Please read this article first about how to calculate an algorithm's complexity, as it provides very useful information and it's explained with practical examples.

Now, you have to rethink your algorithm and get a better time complexity. I won't spoil the solution to you, but I can give you a hint: Think that you don't really need to rotate your array k times by 1 unit, you can instead do it only once by k units.

Hope this helps, good luck in solving the challenge! :)

Comments