You are not logged in. Please login at to post your questions!


Partial Submission of CHEFSUM

problem statement---
my solution -----

how can i edit my code so that it can perform second subtask also

asked 17 Sep '17, 14:11

chopper_pkg's gravatar image

accept rate: 0%

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.


answered 17 Sep '17, 14:35

nrz_2's gravatar image

accept rate: 0%

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

(17 Sep '17, 15:09) chopper_pkg2★

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


answered 17 Sep '17, 16:45

phantomhive's gravatar image

accept rate: 0%

try to do complexity low as O(n^2) won't try to make it in O(n).


answered 17 Sep '17, 19:44

tutejahimanshu's gravatar image

accept rate: 33%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 17 Sep '17, 14:11

question was seen: 330 times

last updated: 17 Sep '17, 19:44