Number of Distinct Averages
EasyPrompt
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
numsand remove it. - Find the maximum number in
numsand 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
2and3is(2 + 3) / 2 = 2.5.
Return the number of distinct averages calculated using the above process.
Note that when there is a tie for a minimum or maximum number, any can be removed.
Example 1:
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:
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 <= 100nums.lengthis even.0 <= nums[i] <= 100
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem statement. In a loop, it repeatedly finds the minimum and maximum values in the current collection of numbers, calculates their average, and then removes them. A HashSet is used to keep track of the unique averages encountered.
Algorithm
- Convert the input array
numsinto aList<Integer>. - Initialize an empty
Set<Double>calledaverages. - Loop while the list is not empty:
- Find the minimum value (
minVal) in the list. - Find the maximum value (
maxVal) in the list. - Calculate
avg = (minVal + maxVal) / 2.0. - Add
avgto theaveragesset. - Remove one occurrence of
minValfrom the list. - Remove one occurrence of
maxValfrom the list.
- Find the minimum value (
- Return the size of the
averagesset.
Walkthrough
We first convert the input array nums into a List (like ArrayList) to facilitate the easy removal of elements. A HashSet<Double> is initialized to store the distinct averages. The main logic is a while loop that continues as long as the list is not empty. Inside the loop, we find the minimum and maximum elements using a linear scan or a helper function like Collections.min() and Collections.max(). The average of these two values is calculated and added to our HashSet, which automatically handles duplicates. Finally, we remove one instance of the minimum value and one instance of the maximum value from the list. It's important to remove by value (e.g., list.remove(Integer.valueOf(minVal))) to avoid issues with duplicate numbers and index-based removal. After the loop terminates, the size of the HashSet gives the number of distinct averages.
import java.util.ArrayList;import java.util.Collections;import java.util.HashSet;import java.util.List;import java.util.Set; class Solution { public int distinctAverages(int[] nums) { List<Integer> list = new ArrayList<>(); for (int num : nums) { list.add(num); } Set<Double> averages = new HashSet<>(); while (!list.isEmpty()) { int minVal = Collections.min(list); int maxVal = Collections.max(list); double avg = (minVal + maxVal) / 2.0; averages.add(avg); list.remove(Integer.valueOf(minVal)); list.remove(Integer.valueOf(maxVal)); } return averages.size(); }}Complexity
Time
O(N^2), where N is the length of `nums`. In each of the N/2 iterations, finding the min/max and removing elements from the list takes O(K) time, where K is the current size of the list. This leads to a complexity of `O(N + (N-2) + ... + 2)`, which is `O(N^2)`.
Space
O(N) to store the list of numbers and the set of averages, where N is the length of `nums`.
Trade-offs
Pros
Very intuitive and directly follows the problem description.
Easy to implement.
Cons
Inefficient due to repeated linear scans to find min/max and remove elements.
Solutions
Solution
class Solution {public int distinctAverages(int[] nums) { Arrays.sort(nums); Set<Integer> s = new HashSet<>(); int n = nums.length; for (int i = 0; i < n >> 1; ++i) { s.add(nums[i] + nums[n - i - 1]); } return s.size(); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.