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;
}
``````

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.
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.