algoadvance

Leetcode 1619. Mean of Array After Removing Some Elements

Problem Statement

The problem is to find the mean of an array after removing some elements. Specifically, you are to remove the smallest 5% and the largest 5% of the elements, and then calculate the mean of the remaining elements.

Clarifying Questions

  1. Input Constraints:
    • Is the input always a list of integers?
    • Can the input list contain negative numbers?
    • What if the list length is less than required to perform the 5% removal?
  2. Output Format:
    • Should the mean be returned as a float or can it be an integer if the result is a whole number?
    • To what precision should the mean be presented (number of decimal places)?

Strategy

  1. Remove outliers:
    • Calculate the 5% of the array’s length.
    • Sort the array to easily remove the smallest and largest 5% of elements.
  2. Calculate the Mean:
    • Sum the elements of the remaining array.
    • Divide by the new length of the array to get the mean.
  3. Handling Edge Cases:
    • If array length is too short (less than 20 elements), handle gracefully since 5% removal from both ends doesn’t make sense (0.05 * n should be at least 1).

Time Complexity

Code

Below is the C++ solution for the given problem:

#include <vector>
#include <algorithm>
#include <numeric>

class Solution {
public:
    double trimMean(std::vector<int>& arr) {
        int n = arr.size();
        int removeCount = n * 0.05;   // 5% of the size
        
        // Sort the array
        std::sort(arr.begin(), arr.end());
        
        // Calculate the sum of the remaining array after removing smallest and largest 5%
        double sum = 0;
        for (int i = removeCount; i < n - removeCount; ++i) {
            sum += arr[i];
        }
        
        // Calculate the new length after removal
        int newLength = n - 2 * removeCount;
        
        // Calculate and return the mean
        return sum / newLength;
    }
};

Explanation

  1. Sorting:
    • The array is sorted to facilitate easy removal of the smallest 5% and largest 5% elements.
  2. Sum Calculation:
    • A loop runs from removeCount to n - removeCount to sum the middle portion of the array.
  3. Mean Calculation:
    • The sum is then divided by the new length of the array to compute the mean.

Test Cases

To verify the correctness of the solution, consider the following test cases:

  1. An array with distinct elements.
  2. An array with repeated elements.
  3. An edge case where the array has fewer than 20 elements.

Example:

int main() {
    Solution sol;
    std::vector<int> arr1 = {1,2,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
    std::cout << sol.trimMean(arr1) << std::endl;  // Expected output: mean after removing 5% smallest and largest elements
    return 0;
}

Be sure to customize the test cases based on the mean of the results after removing the 5% of smallest and largest elements.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI