# 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.

Find integral values k such that sum of expression is minimized
Given 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<=100000$.
What should be the possible value(s) of k such that $f\left(k\right)=|k|+|{X}_{1}+k|+|{X}_{1}+{X}_{2}+k|+\cdots +|{X}_{1}+{X}_{2}+{X}_{3}+\cdots +{X}_{n}+k|$ is minimized .
$|a|$ absolute value of a .
You can still ask an expert for help

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

abortargy
Step 1
I'll describe the algorithmic approach to this problem.
First, replace the sequence $\left\{{X}_{i}{\right\}}_{i=1}^{n}$, defined as ${Y}_{j}=-\sum _{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're then asked to minimize $f\left(x\right)=\sum _{j=0}^{n}|x-{Y}_{j}|$
Step 2
Now, 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 "increasing" terms as there are "decreasing" 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 $\left\{{Y}_{j}\right\}$.
Finding the median can be done easily in time $O\left(n\mathrm{log}n\right)$ by sorting the sequence or, using some clever tricks, can be reduced to O(n) too; yielding a linear algorithm for the whole problem.