Solutions

This easy challenge has, actually, an interesting generalization.

The problem can be quickly solved by noting that the number of elements to select is one less (4) than the length of the input array (5). So we can just sum all the numbers and subtract the result to the max and to the min of the array. The domain is subject to overflow so we have to use a 64-bit integer:

1
2
3
4
5


array<unsigned long long, 5> v;
copy_n(istream_iterator<int>(cin), 5, begin(v));
auto mm = minmax_element(begin(v), end(v));
auto sum = accumulate(begin(v), end(v), 0ll);
cout << (sum-*mm.second) << " " << (sum-*mm.first);

The same idea in Python:

1
2


s = sum(arr)
print(s - max(arr), s - min(arr))

1
2


solve xs = [sum xs - maximum xs, sum xs - minimum xs]
main = interact (unwords . fmap show . solve . fmap read .  words)

Clearly, we can do everything in a single loop instead of calculating min, max and sum in three different scans. We omit the code here.

Note that the time complexity is constant, since the domain is constant.

Another - less efficient - solution consists in sorting the array and then sum the first 4 and the last 4 elements:

1
2
3


import Data.List (sort)
solve = (\xs -> [sum (take 4 xs), sum (drop 1 xs)]) . sort
main = interact (unwords . fmap show . solve . fmap read .  words)

1
2
3
4


array<unsigned long long, 5> v;
copy_n(istream_iterator<int>(cin), 5, begin(v));
sort(begin(v), end(v));
cout << accumulate(begin(v), end(v)-1, 0ull) << " " << accumulate(begin(v)+1, end(v), 0ull);

Summing twice the center of the array can be avoided by using a prefix sum:

1
2
3
4
5


array<unsigned long long, 5> v;
copy_n(istream_iterator<int>(cin), 5, begin(v));
sort(begin(v), end(v));
partial_sum(begin(v), end(v), begin(v));
cout << v[3] << " " << (v[4]-v[0]);

Generalization

Two possibile generalization points of the problem are:

the total number of elements - \(N\),
the number of elements to select - \(K\).

In general, we would like to sum the \(K\) biggest numbers and the \(K\) smallest numbers of the array.

We cannot assume \(K\) is \(N-1\) so the first solution does not work.

The second solution works if we generalize the span of elements to aggregate, it’s quite easy. Generalizing the third solution is easy too, it’s just the matter of fixing the indexes to take:

1
2
3
4
5


array<unsigned long long, N> v;
copy_n(istream_iterator<int>(cin), N, begin(v));
sort(begin(v), end(v));
partial_sum(begin(v), end(v), begin(v));
cout << v[K-1] << " " << (v[N-1]-v[N-K-1]);

Indeed, \(v[K-1]\) is the sum of all the elements until K; whereas, \(v[N-1]\) is the sum of all the elements and \(v[N-K-1]\) is the sum of all the elements from the beginning to \(N-K\) (the span we want to save).

An interesting optimization consists in not sorting at all. Imagine \(N\) is very big but \(K\) is relatively small. The problem reduces to “select” the biggest and the smallest elements of the array. There is a class of algorithms called “selection algorithms” which are able to select the kth smallest number in a sequence by partially sorting the sequence. In C++ we can use nth_element which is guaranteed \(O(N)\):

1
2
3
4
5
6
7


array<unsigned long long, N> v;
copy_n(istream_iterator<int>(cin), N, begin(v));
nth_element(begin(v), begin(v)+K, end(v));
auto minSum = accumulate(begin(v), begin(v)+K, 0ll);
nth_element(begin(v), begin(v)+K, end(v), greater<>{});
auto maxSum = accumulate(begin(v), begin(v)+K, 0ll);
cout << minSum << " " << maxSum;

nth_element works by partitioning the sequence: the element pointed at by \(nth\) (the second parameter) is changed to whatever element would occur in that position if the whole sequence was sorted. All of the elements before this new \(nth\) element are less than or equal to the elements after the new nth element.

Setting \(nth\) to \(K\) results in changing the array so that the smallest elements are moved before \(K\). Similarly, we can repeat the process for the biggest elements just by changing the less predicate.

Benchmark

Here is a quick benchmark where you can compare the solutions and play with the parameters.

sort prefix sum