Number of Distinct Averages — Solution in Python, Java & C++
Number of Distinct Averages solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Number of Distinct Averages is an easy coding problem on arrays, hash table and sorting, asked in Amazon and TCS interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Sorting, Two Pointers
- Asked at: Amazon, TCS
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 100nums.length is even0 <= nums[i] <= 100
Hints for Number of Distinct Averages
Hint 1
Sorting makes the removal order explicit: the
i-th pair iss[i]withs[n-1-i].Hint 2
Two averages are equal exactly when the two sums are equal — so you can avoid floating point entirely.
Hint 3
Count distinct sums with a set.
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
- Sort a copy of
nums. - Walk two pointers inward, pairing
s[i]withs[n-1-i]. - Insert each pair's sum into a set.
- 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.5comparing 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)Java
public static int distinctAverages(int[] nums) {
int[] s = nums.clone();
Arrays.sort(s);
Set<Integer> sums = new HashSet<>();
for (int i = 0, j = s.length - 1; i < j; i++, j--) sums.add(s[i] + s[j]);
return sums.size();
}C++
int distinctAverages(vector<int>& nums) {
vector<int> s = nums;
sort(s.begin(), s.end());
unordered_set<int> sums;
for (int i = 0, j = (int) s.size() - 1; i < j; i++, j--) sums.insert(s[i] + s[j]);
return (int) sums.size();
}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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets