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.

Ismael Molina 2022-07-16 Answered
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 ( 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 .
You can still ask an expert for help

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

abortargy
Answered 2022-07-17 Author has 19 answers
Step 1
I'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're then asked to minimize f ( x ) = 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 { 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.
Did you like this example?
Subscribe for all access

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2022-08-13
Determine the monotonic intervals of the functions
i need to determine the monotonic intervals of this function y = 2 x 3 6 x 2 18 x 7. I tried the below but i am not sure if i am doing it right.
My work: y = 2 x 3 6 x 2 18 x 7 6 x 2 12 x 18 = 0 6 ( x 2 2 x 3 ) = 0 ( x 3 ) ( x + 1 ) x 3 = 0 x + 1 = 0 x = 3 , x = 1
so my function increases when x [ 3 , + [ and decreases when x [ 1 , 3 ] ] , 1 ].
Please i want to know how to solve this problem any help with explanation will be appreciated. thanks in advanced
asked 2022-09-25
Find range of values
Find the range of values of the constant a at which the equation x 3 3 a 2 x + 2 = 0 has 3 different real number roots.
I took the derivative and found that x = a , a. Then I solved for f ( a ) = 0 and f ( a ) = 0 to find that a = 1 , 1.
How do I use this information to find the range of values, or am I on the wrong path completely?
asked 2022-08-26
Even or Odd symmetry
What type of symmetry does the function y = 1 | x | have? Specify the intervals over which the function is increasing and the intervals where it is decreasing.
asked 2022-11-13
Where is this function concave up?
The function is: ( x 2 16 ) 6 .
So I did all the relevant calculations and all my others answers about inflexion points, critical points, extreme points, concave down, increasing and decreasing intervals were correct. But my interval for concave up keeps coming up as wrong.
This is the interval I calculated:
( , 4 ) ( 4 , 4 11 11 ) ( 4 11 11 , 4 ) ( 4 , )
I also tried various alternative ones like:
( , 4 11 11 ) ( 4 11 11 , )
asked 2022-08-11
Is f ( x ) = x 4 x decreasing at x = 4?
I am solving a single variable calculus problem and it asks me to determine the decreasing and decreasing intervals of the function f ( x ) = x 4 x . It's pretty clear that from ] , 8 3 [ the function is increasing but, since the domain of the function goes only until x = 4, should I write that the decreasing interval of the function is ] 8 3 , 4 [ or ] 8 3 , 4 ] ?
asked 2022-10-12
Intervals in which f(x) is Strictly Increasing/Decreasing
Find the intervals in which f ( x ) = sin x + cos x , 0 x 2 π is strictly increasing/decreasing.
First I find the derivative f ( x ) = cos x sin x, then put f ( x ) = 0, getting tan x = 1. The principal solutions of tan x = 1 are x = π / 4 and x = 5 π / 4, which gives the intervals [ 0 , π / 4 ), ( π / 4 , 5 π / 4 ), and ( 5 π / 4 , 2 π ).
After this I am stuck. The book just solves the question by making a table showing the interval, sign of the derivative as positive or negative, and strictly increasing for positive and vice versa.
I just want to know how do they get it positive or negative.It would really help if someone did one for the interval ( π / 4 , 5 π / 4 ).
asked 2022-07-18
Concavity and critical numbers
I am attempting to study for a test, but I forgot how to do all the stuff from earlier in the chapter.
I am attempting to find the intervals where f is increasing and decreasing, min and max values and intervals of concavity and inflection points.
I have f ( x ) = e 2 x + e x . I know that I have to find the derivative, set to zero to find the critical numbers then test points then find the second derivative and do the same to find the concavity but I don't know how to get the derivative of this. Wolfram Alpha gives me a completely different number than what I get.