0
$\begingroup$

I just found out by luck that

 Abs(sum of differences of elements in a sorted array) = array.Max()-array.Min() 

For example, Consider a sorted array, {1 43 65 97 98 99 101}

Abs(1-43-55-97-98-99-101)= 101-1

Does anyone know why?

Thanks in Advance.

$\endgroup$
  • $\begingroup$ Yes. Just write it out... $\endgroup$ – Gilles 'SO- stop being evil' Oct 1 '16 at 22:03
  • $\begingroup$ Higher character encodes higher value. b - a = -(a - b), since array is in ascending order than abs is not needed, simple minus suffice. But why it works for more elements? c - b + b - a = -(a - b + b - c) And this just encodes consecutive differences of sorted elements. I hope you see the pattern. $\endgroup$ – Evil Oct 1 '16 at 22:07
  • 2
    $\begingroup$ Re: "Abs(1-43-55-97-98-99-101)= 101-1": This is not true. $\endgroup$ – ruakh Oct 1 '16 at 23:40
  • $\begingroup$ What does this have to do with computer science, except that you chose to say "array" rather than "sequence of integers"? $\endgroup$ – David Richerby Oct 2 '16 at 9:37
4
$\begingroup$

If you picture these as distances along a road, it should be very intuitive.

If (for example) you start at kilometer #7, then proceed through kilometers #45, #81, and #97, then the distances you travel are 45−7, then 81−45, then 97−81; and the total distance you travel is 97−7. Since the total distance is the sum of the individual distances, 97−7 = (45−7) + (81−45) + (97−81).

This only works for a sorted set, because otherwise you have backtracking, where you cover a certain distance and then "un-cover".

$\endgroup$
  • 4
    $\begingroup$ That's an excellent explanation. For completeness, you should probably say "telescoping sum" and observe that, in $97-81+81-45+45-7$, everything except the first and last term cancels. $\endgroup$ – David Richerby Oct 2 '16 at 9:40

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.