Start learning free

LESSON 266 OF 667 · PAIRS, SORTING & BUILT-INS

Total Without Extremes in C++: accumulate, min_element, max_element

Practice Read the full explanation

You get a vector 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++ · PAIRS, SORTING & BUILT-INS

    Trimmed Total in C++, explained

    Problem overview

    trimmedTotal receives a vector of integers, nums, with 3 to 100 numbers, and returns their sum without one smallest and one largest value. Think of judges' scores where the lowest and highest are dropped. Only one copy of each is dropped: if the smallest value appears twice, the other copy still counts. The same holds for the largest.

    For [7, 9, 6, 8, 10] the answer is 24 (6 and 10 are dropped, leaving 7 + 9 + 8). For [5, 1, 5, 9, 1] it is 11: one 1 and the 9 are dropped, leaving 5 + 5 + 1. For [-4, 3, -2] it is -2.

    Approach: add everything, then take the extremes off once

    The simplest idea is arithmetic. The sum of everything, minus the smallest value, minus the largest value, is the sum with exactly one smallest and one largest removed. Subtracting each value once is what drops exactly one copy, so duplicates take care of themselves. There is no need to find positions or erase anything.

    The three pieces are the built-ins from the chapter: accumulate for the total, min_element for the smallest and max_element for the largest. The last two return positions, so each gets a * to read its value.

    Step by step

    1. Total: accumulate(nums.begin(), nums.end(), 0) into an int named total.
    2. Smallest: *min_element(nums.begin(), nums.end()) into smallest. It yields the value once, even when it appears twice.
    3. Largest: *max_element(nums.begin(), nums.end()) into largest.
    4. Return total - smallest - largest.

    The solution in C++

    class Solution {
public:
    int trimmedTotal(vector<int>& nums) {
        int total = accumulate(nums.begin(), nums.end(), 0);
        int smallest = *min_element(nums.begin(), nums.end());
        int largest = *max_element(nums.begin(), nums.end());
        return total - smallest - largest;
    }
};

    The start value 0 makes the sum an int. That is safe here: at most 100 numbers between -1000 and 1000 can't come near the limits of an int. The star is safe too, because the vector always has at least three numbers; on an empty vector, reading the result of min_element would be undefined behavior.

    Following the second example

    For [5, 1, 5, 9, 1] the three built-ins give a total of 21, a smallest value of 1 and a largest value of 9. Then 21 - 1 - 9 = 11. Both 1s are in the total, only one of them is subtracted, and that matches the rule that the other copy still counts.

    Another way

    You can also sort a copy of the vector and add up everything except its first and last element:

    vector<int> sorted = nums;
sort(sorted.begin(), sorted.end());
int total = 0;
for (size_t i = 1; i + 1 < sorted.size(); i++) {
    total += sorted[i];
}
return total;

    On [5, 1, 5, 9, 1] it also gives 11. The lesson's way is shorter and doesn't need a copy. The loop condition is written i + 1 < sorted.size() rather than i < sorted.size() - 1, because size() is unsigned and subtracting from it wraps around when the vector is empty.

    Edge cases and common mistakes

    • Dropping every copy. Removing all values equal to the smallest would turn [5, 1, 5, 9, 1] into 10 instead of 11.
    • Forgetting the *. min_element returns a position, so int smallest = min_element(...) doesn't compile.
    • All numbers equal. For [4, 4, 4] the smallest and the largest are both 4. Subtracting both leaves one 4, which is correct: one copy of each extreme is dropped.
    • Negative numbers. [-4, 3, -2] gives -2. The formula needs no special case.
    • Starting the sum at 1 by mistake. The start value of accumulate is added to the result, so it must be 0.

    Testing

    • [7, 9, 6, 8, 10] gives 24.
    • [5, 1, 5, 9, 1] gives 11.
    • [-4, 3, -2] gives -2.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free