HackerRank Min-Max Sum

Given five positive integers, find the minimum and maximum values that can be calculated by summing exactly four of the five integers. Then print the respective minimum and maximum values as a single line of two space-separated long integers.

Example

arr = [1, 2, 5, 7, 9 ]

The minimum sum is 1 + 3 + 5 + 7 = 16 and the maximum sum is 3 + 5 + 7 + 9 = 24. The function prints:

16 24

The first step I used to solve this problem was to sort the array.

sortedArray = sorted(arr);

Then to calculate the maximum sum, I calculated the sum of the sorted array minus the first element, this should be the smallest number in the array.

maxSum = sum(arr) - sortedArray[0];

Then to calculate the minimum sum, I calculated the sum of the sorted array minus the last element, this should be the largest number in the array.

minSum = sum(arr) - sortedArray[-1];

Last, print the two calculated sums, maxSum and minSum.

print(minSum, maxSum);

For the specific case of an array with exactly 5 elements, the algorithm is efficient and the time complexity can be considered constant due to the small, fixed size. For larger, variable-sized arrays, the algorithm would have a time complexity of O(n log n) and a space complexity of O(n).

For a more efficient solution, I discovered sorting the array is unnecessary.

    total_sum = sum(arr)
    min_num = min(arr)
    max_num = max(arr)
    
    minSum = total_sum - max_num
    maxSum = total_sum - min_num
    
    print(minSum, maxSum)

I could calculate the total sum and then set the minimum and maximum element in the array to a variable. Then similar to my first solution calculate the minimum sum by subtracting the maximum number from the total sum and the maximum sum by subtracting the minimum number from the total sum.

The overall time complexity is O(n) because it involves summing the array and finding the minimum and maximum values, each of which are O(n) operations.