Get started

Number of Distinct Averages — Easy Problem & Solution

The array nums has even length. Repeat until it is empty: remove the smallest remaining value and the largest remaining value, and record their average.

Problem statement

The array nums has even length. Repeat until it is empty: remove the smallest remaining value and the largest remaining value, and record their average.

When several elements tie for smallest or largest, any one of them may be removed — the multiset of averages is the same either way.

Return how many distinct averages were recorded.

Example 1

Input: nums = [4,1,4,0,3,5]
Output: 2
Explanation: Sorted: 0,1,3,4,4,5. The pairs average 2.5, 2.5 and 3.5 — two distinct values.

Example 2

Input: nums = [1,100]
Output: 1
Explanation: One pair, one average.

Example 3

Input: nums = [9,5,7,8,7,9,8,2,0,7]
Output: 5

Constraints

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

How to solve Number of Distinct Averages

Sorting fixes the pairing, and comparing sums instead of averages keeps everything in integers — dividing by two would only invite floating-point equality bugs.

Approach

  1. Sort a copy of nums.
  2. Walk two pointers inward, pairing s[i] with s[n-1-i].
  3. Insert each pair's sum into a set.
  4. Return the set's size.

Why it works

Each round removes the current minimum and maximum, which in sorted order are exactly the outermost untouched elements. Since all pairs divide by the same 2, two averages match precisely when their sums do.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • Storing averages as floating-point values risks 2.5 comparing unequal to itself across platforms; integer sums are exact.
  • Removing elements from the array as you go is O(n²) and unnecessary.

Reference solution

Python

from typing import List

def distinctAverages(nums: List[int]) -> int:
    s = sorted(nums)
    sums = set()
    i, j = 0, len(s) - 1
    while i < j:
        sums.add(s[i] + s[j])
        i += 1
        j -= 1
    return len(sums)

JavaScript

var distinctAverages = function(nums) {
    var s = nums.slice().sort(function(a, b) { return a - b; });
    var sums = {}, total = 0;
    for (var i = 0, j = s.length - 1; i < j; i++, j--) {
        var key = String(s[i] + s[j]);
        if (sums[key] !== true) { sums[key] = true; total++; }
    }
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue