Start learning free

LESSON 272 OF 674 · TUPLES, SORTING & BUILT-INS

Trimmed Total in C#: Sum, Min and Max

Practice Read the full explanation

You get a List of integers nums. Return their sum without the smallest and the largest value.

Some contests score this way. Each judge gives a score. The lowest and the highest score are dropped. So one very strict or very kind judge can't decide alone.

Drop only one smallest value and one largest value. If the smallest value appears twice, the other copy still counts. The same goes for the largest value.

 

Example 1:

Input: nums = [7, 9, 6, 8, 10]
Output: 24
Explanation: The smallest value is 6 and the largest is 10.
The rest add up to 7 + 9 + 8 = 24.

Example 2:

Input: nums = [5, 1, 5, 9, 1]
Output: 11
Explanation: The smallest value, 1, appears twice.
Only one 1 is dropped, and so is the 9.
5 + 5 + 1 = 11.

Example 3:

Input: nums = [-4, 3, -2]
Output: -2
Explanation: -4 is the smallest value and 3 is the largest.
Only -2 is left.

 

Constraints:

  • nums has 3 to 100 numbers.
  • Every number is between -1000 and 1000.
STEP 1 OF 4
    Ctrl + Enter to check

    C# · TUPLES, SORTING & BUILT-INS

    Trimmed Total in C#, explained

    Problem overview

    TrimmedTotal gets a List<int> named nums and returns their sum without one smallest and one largest value. This is how some contests score: each judge gives a number, and the lowest and the highest are dropped so no single judge decides alone.

    Only one copy of each extreme is dropped. In [5, 1, 5, 9, 1] the smallest value, 1, appears twice, but only one 1 is dropped, together with the 9. The rest, 5 + 5 + 1, is 11. For [7, 9, 6, 8, 10] the answer is 24, and for [-4, 3, -2] it is -2. The list has 3 to 100 numbers, so something always remains.

    Approach

    You do not need to find and remove the extremes from the list. Subtract them instead: the total of everything, minus the smallest value, minus the largest value. Subtracting the smallest value once takes away exactly one copy of it, whether it appears once or five times. The same goes for the largest.

    LINQ provides all three numbers: Sum(), Min() and Max(). Each one makes its own pass over the list.

    Step by step

    1. total is nums.Sum(), the sum of all the numbers.
    2. smallest is nums.Min().
    3. largest is nums.Max().
    4. Return total - smallest - largest.

    The solution in C#

    class Solution {
    public int TrimmedTotal(List<int> nums) {
        int total = nums.Sum();
        int smallest = nums.Min();
        int largest = nums.Max();
        return total - smallest - largest;
    }
}

    Three small variables make each step readable, but return nums.Sum() - nums.Min() - nums.Max(); would do the same.

    Complexity

    Three passes over n numbers are still O(n) time, with O(1) extra space.

    One loop instead of three calls

    You can collect all three numbers in a single pass:

    int total = 0;
int smallest = nums[0];
int largest = nums[0];
foreach (int num in nums) {
    total += num;
    if (num < smallest) smallest = num;
    if (num > largest) largest = num;
}
return total - smallest - largest;

    It returns 11 for [5, 1, 5, 9, 1] and 24 for [7, 9, 6, 8, 10]. This does one pass instead of three, but both versions are O(n), and the built-in calls are shorter and harder to get wrong. Use the loop when you need the three values and more in the same pass.

    Two details of the built-ins are worth knowing. Min() and Max() throw an InvalidOperationException on an empty list, which cannot happen here because the list has at least 3 numbers. And Sum() on ints checks for overflow: a list such as [2000000000, 2000000000] throws an OverflowException instead of wrapping around. With numbers up to 1000, neither matters.

    Another way

    You can sort, then skip the first and the last item: nums.OrderBy(n => n).Skip(1).SkipLast(1).Sum(). It gives 24 for [7, 9, 6, 8, 10] and 11 for [5, 1, 5, 9, 1], like the lesson's code, but sorting costs O(n log n) for no benefit.

    Testing

    Outputs from running the solution:

    numsResult
    [7, 9, 6, 8, 10]24
    [5, 1, 5, 9, 1]11
    [-4, 3, -2]-2
    [4, 4, 4]4

    In the last row the smallest and the largest are the same value, 4. They are still two different items, and each is dropped once, which leaves one 4.

    Common mistakes

    • Removing every copy of the extremes. A RemoveAll or a Where(n => n != smallest) removes both 1s in the second example, so only 5 + 5 is left and the result is 10, not 11.
    • Subtracting before adding. Compute the total of all the numbers first, then take the extremes off.
    • Assuming the list has 3 numbers. The list can have up to 100. The same three calls work for any length of at least 3.
    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free