2465. Number of Distinct Averages LeetCode Solution

In this guide, you will get 2465. Number of Distinct Averages LeetCode Solution with the best time and space complexity. The solution to Number of Distinct Averages problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Number of Distinct Averages solution in C++
4. Number of Distinct Averages solution in Java
5. Number of Distinct Averages solution in Python
6. Additional Resources

Problem Statement of Number of Distinct Averages

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

Complexity Analysis

• Time Complexity: O(\texttt{sort} + n\log n)
• Space Complexity: O(n)

2465. Number of Distinct Averages LeetCode Solution in C++

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();
  }
};
/* code provided by PROGIEZ */

2465. Number of Distinct Averages LeetCode Solution in Java

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();
  }
}
// code provided by PROGIEZ

2465. Number of Distinct Averages LeetCode Solution in Python

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)
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.