By grouping all the items within an array into pairs and getting their absolute differences, what is the minimum sum of their absolute differences?
Example:
[4, 1, 2, 3] should return 2 because |1 - 2| + |3 - 4| = 2
[1, 3, 3, 4, 5] should return 1 because |3 - 3| + |4 - 5| = 1
Getting the result for arrays with an even length is pretty easy, because it just requires sorting the array and getting the differences between numbers right next to each other.
However, arrays with an odd length are pretty hard because the addition of an extra number. Thus, my current solution for odd length arrays is to remove each number and check the sum using the even-length array approach.
Current solution:
def smallest_sum(arr):
arr = sorted(arr)
if len(arr) % 2 == 0:
return even_arr_sum(arr)
else:
return odd_arr_sum(arr)
def even_arr_sum(arr):
total = 0
for i in range(0, len(arr), 2):
total += arr[i+1] - arr[i]
return total
def odd_arr_sum(arr):
total = 0
for i in range(len(arr)):
s = even_arr_sum(arr[:i] + arr[i+1:])
if total == 0 or s < total:
total = s
return total
assert smallest_sum([4, 1, 2, 3]) == 2
assert smallest_sum([1, 3, 3, 4, 5]) == 1
However, this is extremely slow and gives a time of n2. Is there a smarter way to handle arrays with an odd length?
Imagine you have sorted seven numbers A to G and you leave out A, thus calculating (C-B)+(E-D)+(G-F). That's adding or subtracting them like this:
A B C D E F G
- + - + - + (leaving out A)
And this is how it looks in general, for leaving out each of the numbers:
A B C D E F G
- + - + - + (leaving out A)
- + - + - + (leaving out B)
- + - + - + ...
- + - + - +
- + - + - +
- + - + - +
- + - + - +
From one row to the next, there's little change. So first compute the total for leaving out A. Then for the total for leaving out B, simply subtract A and add B. And so on.