Find integral values k such that sum of expression is minimizedGiven n values X 1 , X 2 , . . . . , X n , where X i can be positive or negative.The absolute values of X i will be less than 100000, also n &lt;= 100000.What should be the possible value(s) of k such that f ( k ) = | k | + | X 1 + k | + | X 1 + X 2 + k | + ⋯ + | X 1 + X 2 + X 3 + ⋯ + X n + k | is minimized . | a | absolute value of a .

Question

Find integral values k such that sum of expression is minimizedGiven n values       X    1    ,      X    2    ,  .  .  .  .  ,      X    n  , where       X    i   can be positive or negative.The absolute values of       X    i   will be less than 100000, also   n  &amp;lt;=  100000.What should be the possible value(s) of k such that   f  (  k  )  =      |    k      |    +      |        X    1    +  k      |    +      |        X    1    +      X    2    +  k      |    +  ⋯  +      |        X    1    +      X    2    +      X    3    +  ⋯  +      X    n    +  k      |   is minimized .      |    a      |   absolute value of a .

abortargy · Accepted Answer

Step 1I&#039;ll describe the algorithmic approach to this problem.First, replace the sequence   {      X    i        }          i      =      1        n  , defined as       Y    j    =  −      ∑          i      =      1        j        X    i  . This can be performed in linear time, since we just need to keep adding one term at time to the partial sum.We&#039;re then asked to minimize   f  (  x  )  =      ∑          j      =      0        n        |    x  −      Y    j        |  Step 2Now, imagine that x starts from some number which is strictly smaller than all the       Y    j   and keeps moving towards greater values. Initially, all the absolute values in the sum keep decreasing. This changes once x crosses the first       Y    j  ; that particular term reaches zero and starts increasing again as x moves further. Crossing more and more of the       Y    j  , more and more terms start increasing until there are as many &quot;increasing&quot; terms as there are &quot;decreasing&quot; ones. Since all the increasing and decreasing happens at the same rate, this is precisely the point where the value of the sum is minimized; moving further towards greater x can only add more of the increasing ones and remove decreasing ones; thus increasing the value of the sum again.We are thus seeking the point which has equal number of       Y    j   to the right and left of it (this point might not be determined uniquely; in some cases it might be any point of interval between two consecutive       Y    j  ); which means x is the median of the sequence   {      Y    j    }.Finding the median can be done easily in time   O  (  n  log  ⁡  n  ) by sorting the sequence or, using some clever tricks, can be reduced to O(n) too; yielding a linear algorithm for the whole problem.

Given n values X_1, X_2,....,X_n, where X_i can be positive or negative. The absolute values of Xi will be less than 100000, also n leq 100000. What should be the possible value(s) of k such that f(k)=|k|+|X_1+k|+|X_1+X_2+k|+⋯+|X_1+X_2+X_3+⋯+X_n+k| is minimized. |a| = absolute value of a.

Answered question

Answer & Explanation

New Questions in Integral Calculus