Skip to content

2465. Number of Distinct Averages 👍

  • Time: $O(\texttt{sort} + n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
 public:
  int distinctAverages(vector<int>& nums) {
    const int n = nums.size();
    unordered_set<int> sums;

    ranges::sort(nums);

    for (int i = 0; i < n / 2; ++i)
      sums.insert(nums[i] + nums[n - 1 - i]);

    return sums.size();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
  public int distinctAverages(int[] nums) {
    final int n = nums.length;
    Set<Integer> sums = new HashSet<>();

    Arrays.sort(nums);

    for (int i = 0; i < n / 2; ++i)
      sums.add(nums[i] + nums[n - 1 - i]);

    return sums.size();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  def distinctAverages(self, nums: list[int]) -> int:
    n = len(nums)
    sums = set()

    nums.sort()

    for i in range(n // 2):
      sums.add(nums[i] + nums[n - 1 - i])

    return len(sums)