Problem

You are given a 0-indexed integer array nums of even length.

As long as nums is not empty, you must repetitively:

  • Find the minimum number in nums and remove it.
  • Find the maximum number in nums and remove it.
  • Calculate the average of the two removed numbers.

The average of two numbers a and b is (a + b) / 2.

  • For example, the average of 2 and 3 is (2 + 3) / 2 = 2.5.

Return the number ofdistinct averages calculated using the above process.

Note that when there is a tie for a minimum or maximum number, any can be removed.

Examples

Example 1

1
2
3
4
5
6
7

Input: nums = [4,1,4,0,3,5]
Output: 2
Explanation:
1. Remove 0 and 5, and the average is (0 + 5) / 2 = 2.5. Now, nums = [4,1,4,3].
2. Remove 1 and 4. The average is (1 + 4) / 2 = 2.5, and nums = [4,3].
3. Remove 3 and 4, and the average is (3 + 4) / 2 = 3.5.
Since there are 2 distinct numbers among 2.5, 2.5, and 3.5, we return 2.

Example 2

1
2
3
4

Input: nums = [1,100]
Output: 1
Explanation:
There is only one average to be calculated after removing 1 and 100, so we return 1.

Constraints

  • 2 <= nums.length <= 100
  • nums.length is even.
  • 0 <= nums[i] <= 100

Solution

Method 1 – Two Pointers with Set

Intuition

Sort the array. In each step, remove the smallest and largest elements, compute their average, and store it in a set. The number of distinct averages is the size of the set.

Approach

  1. Sort the array.
  2. Use two pointers (left, right) to pick min and max, compute average, and add to a set.
  3. Return the size of the set.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include <vector>
#include <set>
#include <algorithm>
using namespace std;
class Solution {
public:
    int distinctAverages(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        set<double> s;
        int l = 0, r = nums.size()-1;
        while (l < r) {
            s.insert((nums[l]+nums[r])/2.0);
            ++l; --r;
        }
        return s.size();
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func distinctAverages(nums []int) int {
    sort.Ints(nums)
    s := map[float64]struct{}{}
    l, r := 0, len(nums)-1
    for l < r {
        avg := float64(nums[l]+nums[r])/2.0
        s[avg]=struct{}{}
        l++; r--
    }
    return len(s)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

import java.util.*;
class Solution {
    public int distinctAverages(int[] nums) {
        Arrays.sort(nums);
        Set<Double> set = new HashSet<>();
        int l = 0, r = nums.length-1;
        while (l < r) {
            set.add((nums[l]+nums[r])/2.0);
            l++; r--;
        }
        return set.size();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun distinctAverages(nums: IntArray): Int {
        nums.sort()
        val set = mutableSetOf<Double>()
        var l = 0; var r = nums.size-1
        while (l < r) {
            set.add((nums[l]+nums[r])/2.0)
            l++; r--
        }
        return set.size
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def distinctAverages(self, nums: List[int]) -> int:
        nums.sort()
        s = set()
        l, r = 0, len(nums)-1
        while l < r:
            s.add((nums[l]+nums[r])/2)
            l += 1; r -= 1
        return len(s)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

use std::collections::HashSet;
impl Solution {
    pub fn distinct_averages(nums: Vec<i32>) -> i32 {
        let mut nums = nums;
        nums.sort();
        let mut s = HashSet::new();
        let (mut l, mut r) = (0, nums.len()-1);
        while l < r {
            s.insert((nums[l]+nums[r]) as f64 / 2.0);
            l += 1; r -= 1;
        }
        s.len() as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

function distinctAverages(nums: number[]): number {
    nums.sort((a,b)=>a-b);
    const set = new Set<number>();
    let l = 0, r = nums.length-1;
    while (l < r) {
        set.add((nums[l]+nums[r])/2);
        l++; r--;
    }
    return set.size;
}

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(n)