so i solved " CodeChef: Practical coding for everyone " this problem but it shows time limit exceeded error so i went to see other’s solution and landed upon an accepted solution “CodeChef: Practical coding for everyone” which is similar to mine solution.
so the problem here is that the both solution use two for loops but when i execute mine solution it takes 5.01 sec to compile and the solution i landed upon which submitted by someone else takes 0.06 sec . so i am unable to understand why is that, can anyone help to understand .
You code simulates the right rotation operation by reconstructing the entire input list N times. The overall time-complexity for this approach is O(N^2). On the other hand, the time-complexity of finding the maximum sum of all N-1 adjacent pairs (A_i,A_{i+1}) where 1 \leq i \leq N-1, in addition to the pair (A_N,A_1), is O(N).
1 Like
so the overall complexity of my program is O(2N^2) then? can you also check the solution which is submitted by someone “CodeChef: Practical coding for everyone” else which similar to mine code and also used max() function then why is that his program taking less then 1 sec?
The other solution with less than 0.1 sec is similar only in the outer loop for reading the different test cases, and in the way the input array size N and the input list A is read. The time-complexity of summing adjacent elements in the list is O(1), while the time-complexity of reconstructing the input list in the inner loop of your code is O(N) per iteration.
You can check my solution of the problem as well whose execution time is less than 0.1 sec as well.
1 Like
The following is measurement of the elapsed-time in executing the inner loop of your code for increasing values of N.
2 Likes