# Number of Distinct Averages
**Difficulty:** EASY
[External](https://leetcode.com/problems/number-of-distinct-averages)
Canonical: https://scaleengineer.com/dsa/problems/number-of-distinct-averages
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
---
## 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 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 <= 100`
* `nums.length` is even.
* `0 <= nums[i] <= 100`

# Approaches
## Simulation with Repeated Searching and Removal
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.
**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`.
**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.
### Explanation
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.

```java
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();
    }
}
```
### Algorithm
- Convert the input array `nums` into a `List<Integer>`.
- Initialize an empty `Set<Double>` called `averages`.
- 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 `avg` to the `averages` set.
  - Remove one occurrence of `minVal` from the list.
  - Remove one occurrence of `maxVal` from the list.
- Return the size of the `averages` set.

## Sorting and Two Pointers
A more efficient approach involves sorting the array first. Once sorted, the smallest element is always at the beginning of the remaining portion of the array, and the largest is at the end. We can use two pointers, one at the start and one at the end, moving inwards to pair the minimum and maximum elements.
**Time:** O(N log N), dominated by the sorting step. The two-pointer traversal is `O(N)`. · **Space:** O(N) for the `HashSet`. Some sorting algorithms might use `O(log N)` or `O(N)` auxiliary space, but `Arrays.sort` in Java for primitives has an average space complexity of `O(log N)`. The `HashSet` can store up to N/2 elements, so the dominant factor is `O(N)`.
**Pros:** Significantly more efficient than the simulation approach.; The logic is clean and easy to follow.
**Cons:** The `O(N log N)` time complexity from sorting is not the absolute fastest possible, given the constraints.; It modifies the input array, which might not be desirable in some contexts (though a copy could be made).
### Explanation
The key insight is that the process of repeatedly taking the minimum and maximum element is equivalent to pairing the i-th smallest element with the i-th largest element. First, we sort the input array `nums` in ascending order. We initialize a `HashSet<Double>` to store the distinct averages. Two pointers, `left` and `right`, are initialized to the start (`0`) and end (`nums.length - 1`) of the sorted array, respectively. We loop as long as `left < right`. In each iteration, the current minimum is `nums[left]` and the current maximum is `nums[right]`. We calculate their average and add it to the `HashSet`. We then "remove" these elements by moving the pointers inward: `left++` and `right--`. The loop continues until the pointers meet or cross, at which point all numbers have been paired. The final answer is the size of the `HashSet`.

```java
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int distinctAverages(int[] nums) {
        Arrays.sort(nums);
        Set<Double> averages = new HashSet<>();
        int left = 0;
        int right = nums.length - 1;
        
        while (left < right) {
            double avg = (nums[left] + nums[right]) / 2.0;
            averages.add(avg);
            left++;
            right--;
        }
        
        return averages.size();
    }
}
```
### Algorithm
- Sort the input array `nums`.
- Initialize an empty `Set<Double>` called `averages`.
- Initialize two pointers: `left = 0` and `right = nums.length - 1`.
- Loop while `left < right`:
  - Calculate `avg = (nums[left] + nums[right]) / 2.0`.
  - Add `avg` to the `averages` set.
  - Increment `left` and decrement `right`.
- Return the size of the `averages` set.

## Frequency Array (Counting Sort) and Two Pointers
This approach leverages the constraint that the numbers in the array are small (0 to 100). Instead of a general-purpose sort, we can use a frequency array (or counting sort) to count the occurrences of each number. Then, we can use two pointers on this frequency array to find the current min and max values to pair up.
**Time:** O(N + K), where N is the length of `nums` and K is the range of values (101). Populating the `counts` array is `O(N)`. The two-pointer scan over the `counts` array takes `O(N/2 + K)` time because we form N/2 pairs and the pointers traverse the range K at most once. Thus, the total complexity is `O(N + K)`. · **Space:** O(N + K). We need `O(K)` space for the `counts` array and `O(N/2)` space for the `HashSet` in the worst case, where N is the number of elements and K is the range of values (101).
**Pros:** The most efficient approach with linear time complexity.; Optimal for the given constraints on the range of numbers.
**Cons:** This approach is not general. It relies heavily on the small, non-negative integer range of the input values. It would be impractical if numbers were large or non-integers.
### Explanation
Since `0 <= nums[i] <= 100`, we can create an integer array `counts` of size 101. We iterate through the input `nums` and populate `counts`, where `counts[x]` stores the frequency of the number `x`. Similar to the sorting approach, we use two pointers, `minVal` and `maxVal`, initialized to `0` and `100` respectively. These pointers will scan the `counts` array. We loop `nums.length / 2` times to form all the pairs. In each iteration, we advance `minVal` from its current position until we find a number that exists (i.e., `counts[minVal] > 0`). Similarly, we move `maxVal` downwards until we find an existing number (`counts[maxVal] > 0`). These `minVal` and `maxVal` are the current smallest and largest numbers. We calculate their average and add it to a `HashSet`. We then decrement their counts in the `counts` array to mark them as "used". This process is repeated until all pairs are formed. This method avoids the `O(N log N)` sorting cost and achieves linear time complexity.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int distinctAverages(int[] nums) {
        int[] counts = new int[101];
        for (int num : nums) {
            counts[num]++;
        }
        
        Set<Double> averages = new HashSet<>();
        int minVal = 0;
        int maxVal = 100;
        int pairsFound = 0;
        int n = nums.length;
        
        while (pairsFound < n / 2) {
            while (counts[minVal] == 0) {
                minVal++;
            }
            while (counts[maxVal] == 0) {
                maxVal--;
            }
            
            double avg = (minVal + maxVal) / 2.0;
            averages.add(avg);
            
            counts[minVal]--;
            counts[maxVal]--;
            pairsFound++;
        }
        
        return averages.size();
    }
}
```
### Algorithm
- Create a frequency array `counts` of size 101, initialized to zeros.
- Iterate through `nums` and increment `counts[num]` for each number.
- Initialize an empty `Set<Double>` `averages`.
- Initialize two pointers: `minVal = 0` and `maxVal = 100`.
- Loop `nums.length / 2` times:
  - Increment `minVal` while `counts[minVal]` is 0.
  - Decrement `maxVal` while `counts[maxVal]` is 0.
  - Calculate `avg = (minVal + maxVal) / 2.0`.
  - Add `avg` to the `averages` set.
  - Decrement `counts[minVal]` and `counts[maxVal]`.
- Return the size of the `averages` set.

# Solutions
### Java

```java
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();
  }
}

```

### CPP

```cpp
class Solution {
public:
  int distinctAverages(vector<int> &nums) {
    sort(nums.begin(), nums.end());
    unordered_set<int> s;
    int n = nums.size();
    for (int i = 0; i < n >> 1; ++i) {
      s.insert(nums[i] + nums[n - i - 1]);
    }
    return s.size();
  }
};

```

### Python

```python
class Solution:
    def distinctAverages(self, nums: List[int]) -> int: nums . sort() return len(set(nums[i] + nums[- i - 1] for i in range(len(nums) >> 1)))

```