0
$\begingroup$

Given an array of N elements some of which are positive and some are negative now some positive valued elements can give their value to negative valued elements.Now we need to make whole array as zero but if D is distance between two indexes i and j and D=|j-i| then sum of all these D should be minimum.

Note It is always possible to make array zero which means sum of all positive elements is equal to sum of negative elements.

Like say we have array of $3$ elements $[1,2,-3]$ then here answer is $4$ as $|2-3|+|2-3|+|1-3|=4$.

Explanation : $2$nd index element will give $1$ to $3$rd element then array become $[1,1,-2]$ then again $2$nd index element will give $1$ to $3$rd element then array become $[1,0,-1]$ then $1$st index element will give $1$ to $3$rd element then array become $[0,0,0]$ .How to find this minimum cost.?

$\endgroup$
0
$\begingroup$

Think of "charges" moving along a wire. The cost is the total distance travelled by all (positive or negative) charges until annihilation. Hence that cost for an array $a_1,\ldots, a_n$ is the same as the cost for the shorter array $a_1,\ldots,a_{n-2},a_{n-1}+a_n$ plus the cost $|a_n|$ of moving the carges away from the last entry. You will note from this that the total cost can be evaluated with a simple loop in $O(n)$ time (and in fact can be computed "online", i.e. without the need to even store the complete array at all).

$\endgroup$
  • $\begingroup$ Can you explain with some suitable example ? $\endgroup$ – user119249 Oct 3 '14 at 10:28
  • $\begingroup$ How O(N) ? Am not getting you.What you mean by cost for an array a1,…,an is the same as the cost for the shorter array a1,…,an−2,an−1+an plus the cost |an| of moving the carges away from the last entry. $\endgroup$ – user119249 Oct 3 '14 at 10:29
  • $\begingroup$ I think you got it wrong.As the negative element need not to be present only at last of array.It can be in between too $\endgroup$ – user119249 Oct 3 '14 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.