Skip to content

3194. Minimum Average of Smallest and Largest Elements

SourceWeekly Contest 403 Q1DifficultyEasyRating1194

Description

You have an array of floating point numbers averages which is initially empty. You are given an array nums of n integers where n is even.

You repeat the following procedure n / 2 times:

  • Remove the smallest element, minElement, and the largest element maxElement, from nums.
  • Add (minElement + maxElement) / 2 to averages.

Return the minimum element in averages.

 

Example 1:

Input: nums = [7,8,3,4,15,13,4,1]

Output: 5.5

Explanation:

step nums averages
0 [7,8,3,4,15,13,4,1] []
1 [7,8,3,4,13,4] [8]
2 [7,8,4,4] [8,8]
3 [7,4] [8,8,6]
4 [] [8,8,6,5.5]
The smallest element of averages, 5.5, is returned.

Example 2:

Input: nums = [1,9,8,3,10,5]

Output: 5.5

Explanation:

step nums averages
0 [1,9,8,3,10,5] []
1 [9,8,3,5] [5.5]
2 [8,5] [5.5,6]
3 [] [5.5,6,6.5]

Example 3:

Input: nums = [1,2,3,7,8,9]

Output: 5.0

Explanation:

step nums averages
0 [1,2,3,7,8,9] []
1 [2,3,7,8] [5]
2 [3,7] [5,5]
3 [] [5,5,5]

 

Constraints:

  • 2 <= n == nums.length <= 50
  • n is even.
  • 1 <= nums[i] <= 50

Solutions

Solution 1: Sorting

Thinking

Each step averages the current minimum and maximum; the answer is the smallest of those averages. A multiset simulation works, but the endpoints after sorting already form the pairs.

The \(i\)-th smallest pairs with the \(i\)-th largest, averaging \((nums[i]+nums[n-1-i])/2\).

Take the minimum of those sums for \(i=0..n/2-1\) and divide by two.

First, we sort the array \(\textit{nums}\). Then, we start taking elements from both ends of the array, calculating the sum of the two elements, and taking the minimum value. Finally, we return the minimum value divided by 2 as the answer.

The time complexity is \(O(n \log n)\), and the space complexity is \(O(\log n)\), where \(n\) is the length of the array \(\textit{nums}\).

1
2
3
4
5
class Solution:
    def minimumAverage(self, nums: List[int]) -> float:
        nums.sort()
        n = len(nums)
        return min(nums[i] + nums[-i - 1] for i in range(n // 2)) / 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public double minimumAverage(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int ans = 1 << 30;
        for (int i = 0; i < n / 2; ++i) {
            ans = Math.min(ans, nums[i] + nums[n - i - 1]);
        }
        return ans / 2.0;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    double minimumAverage(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ans = 1 << 30, n = nums.size();
        for (int i = 0; i < n; ++i) {
            ans = min(ans, nums[i] + nums[n - i - 1]);
        }
        return ans / 2.0;
    }
};

1
2
3
4
5
6
7
8
9
func minimumAverage(nums []int) float64 {
    sort.Ints(nums)
    n := len(nums)
    ans := 1 << 30
    for i, x := range nums[:n/2] {
        ans = min(ans, x+nums[n-i-1])
    }
    return float64(ans) / 2
}

1
2
3
4
5
6
7
8
9
function minimumAverage(nums: number[]): number {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let ans = Infinity;
    for (let i = 0; i * 2 < n; ++i) {
        ans = Math.min(ans, nums[i] + nums[n - 1 - i]);
    }
    return ans / 2;
}

1
2
3
4
5
6
7
8
impl Solution {
    pub fn minimum_average(mut nums: Vec<i32>) -> f64 {
        nums.sort();
        let n = nums.len();
        let ans = (0..n / 2).map(|i| nums[i] + nums[n - i - 1]).min().unwrap();
        ans as f64 / 2.0
    }
}

Comments