problem statement— CodeChef: Practical coding for everyone
my solution ----- CodeChef: Practical coding for everyone
how can i edit my code so that it can perform second subtask also
You are using a brute force approach whose complexity is n^2.By understanding the question you can solve the solution in O(n). We can observe that val[i] is used in both prefix(i) and suffix(i). Total sum of prefix(i) +sufix(i) will be equal to sum of array + val[i] (val[i] is in both prefix and suffix). So to minimize the sum we have to find the index( convert the index to 1-based) with minimum value.
You can use prefix_sum and sufix_sum array calculated before hand so that u dont need to do it every time it will reduce your complexity of your code from O(N^2) to O(N) here is my solution
try to do complexity low as O(n^2) won’t work.so try to make it in O(n).
https://www.codechef.com/viewsolution/15191274
ok but after doing that it only reduce the complexity of the program but i want to know how can i edit my code so that i can take constraints 1 ≤ N, A[i] ≤ 10^5