2465. Number of Distinct Averages


Problem Description

The given problem involves an array of integers nums, which has an even number of elements. We are instructed to perform a series of operations until the array becomes empty. In each operation, we must remove the smallest and the largest numbers from the array then calculate their average. This process is repeated until no numbers are left in the array. Our goal is to determine how many distinct averages we can get from these operations. It is important to note that in case of multiple instances of the minimum or maximum values, any occurrence of them can be removed.

Intuition

Considering that we need to find the minimum and maximum values of the array to calculate averages, a straightforward approach would be to sort the array first. With the array sorted, the minimum value will always be at the beginning of the array, and the maximum value will be at the end.

By sorting the array, we simplify the problem as follows:

  • The minimum number of the array will be nums[0], the second smallest nums[1], and so on.
  • The maximum number will be nums[-1], the second-largest nums[-2], and similar for the other elements.

After each operation of removing the smallest and largest elements, the subsequent smallest and largest elements become the adjacent values (the next elements in the sorted array). Therefore, we avoid the need for repeated searching for min and max in an unsorted array.

To find the distinct averages:

  • We iterate over half of the list (len(nums) >> 1), since every operation removes two elements.
  • For each iteration, we calculate the average of nums[i] and nums[-i - 1], which is effectively the average of the ith smallest and ith largest value in the array.
  • We use a set to collect these averages, which automatically ensures that only distinct values are kept.
  • The length of this set is the number of distinct averages we have calculated, which is what we want to return.

This algorithm is efficient because it sorts the array once, and then simply iterates through half of the array, resulting in a complexity of O(n log n) due to the sorting step.

Solution Approach

The solution uses Python's built-in sorting mechanism to organize the elements in nums from the smallest to the largest. By sorting the array, the algorithm simplifies the process of finding the smallest and largest elements in each step.

Here's a step-by-step explanation of the solution:

  • First, nums.sort() is called to sort the array in place. After the sort, nums[0] will contain the smallest value, and nums[-1] will contain the largest value, and so on for the ith smallest and ith largest elements.

  • The generator expression (nums[i] + nums[-i - 1] for i in range(len(nums) >> 1)) then iterates through the first half of the elements in the sorted list. The expression len(nums) >> 1 is an efficient way to divide the length of nums by 2, using a bit-shift to the right.

  • In each iteration, nums[i] + nums[-i - 1] calculates the sum of the ith smallest and ith largest element, which is equivalent to finding the sum of the elements at the symmetric positions from the start and the end of the sorted array.

  • This sum is divided by 2 to calculate the average, but since the division by 2 is redundant when only interested in uniqueness (it does not affect whether the values are unique), it is not performed explicitly.

  • All of these sums (representing the averages) are then collected into a set. As sets only store distinct values, any duplicate averages calculated during the iteration will only appear once.

  • Finally, len(set(...)) returns the number of distinct elements in the set, which corresponds to the number of distinct averages that were calculated.

In terms of data structures and patterns used:

  • An array/list data structure is the primary structure utilized.
  • Sorting is the main algorithmic pattern applied.
  • A set is used to deduplicate values and count distinct elements.

This solution is particularly elegant because it leverages the sorted order of the array and the property of set collections to avoid unnecessary computations and simplify logic.

Example Walkthrough

Let's use a small example to illustrate the solution approach described above.

Suppose we have the following array:

1nums = [1, 3, 2, 6, 4, 5]

The problem requires us to continually remove the smallest and largest numbers, calculate their average, and determine the number of distinct averages we can get from these operations. Let's walk through this step by step:

Step 1: Sort the array. Sorting the array in increasing order will give us:

1nums.sort()  # After sorting: [1, 2, 3, 4, 5, 6]

Step 2: Initialize an empty set to store unique averages.

1averages = set()

Step 3: Remove the smallest and largest numbers and calculate their averages.

1# Since there are six elements, we iterate over half of that, which is three elements.
2length_half = len(nums) >> 1  # Equivalent to dividing the length of nums by 2
3
4for i in range(length_half):
5    minimum = nums[i]  # ith smallest after sorting
6    maximum = nums[-i - 1]  # ith largest after sorting
7    # We calculate the sum since the division by 2 won't affect uniqueness
8    avg = minimum + maximum  
9    averages.add(avg)  # Add the sum (representing the average) to the set of unique averages

Iteration example:

  • First iteration for i=0: minimum is nums[0] which is 1; maximum is nums[-1] which is 6. Their sum is 1 + 6 = 7. Add 7 to the set of averages.
  • Second iteration for i=1: minimum is nums[1] which is 2; maximum is nums[-2] which is 5. Their sum is 2 + 5 = 7. As 7 is already present in the set, it's not added again.
  • Third iteration for i=2: minimum is nums[2] which is 3; maximum is nums[-3] which is 4. Their sum is 3 + 4 = 7. Again, already present.

Step 4: The set of averages now has distinct sums. After the iterations, our set of averages will be:

1averages = {7}

Step 5: Get the number of unique averages. Finally, we get the unique count by measuring the length of the set averages:

1unique_averages_count = len(averages)  # This will be 1

Based on this example, even though we calculated the average (its sum representation) three times, our set contains only one element. Therefore, the number of distinct averages in the nums array we started with is 1.

This example illustrates that the solution approach is efficient and avoids unnecessary complexity by using sorting, taking advantage of the properties of the set, and simplifying the problem into one that can be solved in linear time after sorting.

Python Solution

1from typing import List
2
3class Solution:
4    def distinct_averages(self, nums: List[int]) -> int:
5        # Sort the input list of numbers
6        nums.sort()
7      
8        # Initialize an empty set to store unique averages
9        unique_averages = set()
10      
11        # Calculate the average of each pair of numbers, one from the start
12        # and one from the end of the list, moving towards the middle
13        for i in range(len(nums) // 2):  # Integer division to get half-way index
14            # Calculate the sum of the pair and add it to the set.
15            # We don't actually divide by 2 since it's the average of two nums and
16            # we are interested in distinct averages. The div by 2 won't affect uniqueness.
17            average = nums[i] + nums[-i - 1]
18          
19            # Add the calculated sum (which represents an average) to the set
20            unique_averages.add(average)
21      
22        # Return the number of unique averages
23        return len(unique_averages)
24

Java Solution

1class Solution {
2    public int distinctAverages(int[] nums) {
3        // Sort the array to facilitate pairing of elements
4        Arrays.sort(nums);
5      
6        // Create an array to count distinct averages.
7        // Since the problem constraints are not given, assuming 201 is the maximum value based on the given code.
8        int[] count = new int[201];
9      
10        // Get the length of the nums array
11        int n = nums.length;
12      
13        // Initialize the variable to store the number of distinct averages
14        int distinctCount = 0;
15      
16        // Loop through the first half of the sorted array
17        for (int i = 0; i < n / 2; ++i) {
18            // Calculate the average of the ith and its complement element (nums[i] + nums[n - i - 1]) 
19            // and increase the count for this average.
20            // We do not actually compute the average to avoid floating point arithmetic
21            // since the problem seems to be working with integer addition only.
22            int sum = nums[i] + nums[n - i - 1];
23            if (++count[sum] == 1) {
24                // If the count of a particular sum is 1, it means it is distinct, increase the distinctCount
25                ++distinctCount;
26            }
27        }
28      
29        // Return the total count of distinct averages found
30        return distinctCount;
31    }
32}
33

C++ Solution

1#include <algorithm> // For std::sort
2#include <vector>
3using namespace std;
4
5class Solution {
6public:
7    int distinctAverages(vector<int>& nums) {
8        // Sort the input vector in non-decreasing order.
9        sort(nums.begin(), nums.end());
10      
11        // Initialize a count array of size 201 to store 
12        // the frequency of the sum of pairs.
13        int countArray[201] = {};
14      
15        // Obtain the size of the input vector.
16        int numElements = nums.size();
17      
18        // Initialize a variable to store the count of distinct averages.
19        int distinctCount = 0;
20      
21        // Loop through the first half of the vector as we are creating pairs
22        // that consist of one element from the first half and one from the second.
23        for (int i = 0; i < numElements / 2; ++i) {
24            // Calculate the sum of the current pair: the i-th element and its corresponding
25            // element in the second half of the array (mirror position regarding the center).
26            int pairSum = nums[i] + nums[numElements - i - 1];
27          
28            // If this sum appears for the first time, increase the distinct count.
29            if (++countArray[pairSum] == 1) {
30                ++distinctCount;
31            }
32        }
33      
34        // Return the count of distinct averages.
35        return distinctCount;
36    }
37};
38

Typescript Solution

1// This function calculates the number of distinct averages that can be formed
2// by the sum of pairs taken from the start and end of a sorted array.
3function distinctAverages(nums: number[]): number {
4    // Sort the array in non-decreasing order
5    nums.sort((a, b) => a - b);
6
7    // Initialize a frequency array to keep track of the distinct sums
8    const frequency: number[] = Array(201).fill(0);
9
10    // Variable to hold the number of distinct averages
11    let distinctCount = 0;
12
13    // Determine the length of 'nums' array
14    const length = nums.length;
15
16    // Iterate over the first half of the sorted array
17    for (let i = 0; i < length >> 1; ++i) {
18        // Calculate the sum of the current element and its corresponding element from the end
19        const sum = nums[i] + nums[length - i - 1];
20
21        // Increase the frequency count for the calculated sum
22        frequency[sum]++;
23
24        // If this is the first time the sum appears, increment the distinctCount
25        if (frequency[sum] === 1) {
26            distinctCount++;
27        }
28    }
29
30    // Return the total number of distinct averages
31    return distinctCount;
32}
33

Time and Space Complexity

The time complexity of the code above is O(n log n) and the space complexity is O(n).

Time Complexity

  1. nums.sort(): Sorting the list of n numbers has a time complexity of O(n log n).

  2. The list comprehension set(nums[i] + nums[-i - 1] for i in range(len(nums) >> 1)) iterates over the sorted list but only up to the halfway point, which is n // 2 iterations. Although the iteration is linear in time with respect to the number of elements it processes, the dominant term for time complexity comes from the sorting step.

Therefore, combining both steps we get O(n log n), which is the overall time complexity.

Space Complexity

  1. The sorted in-place method nums.sort() does not use additional space other than a few variables for the sorting algorithm itself (O(1) space).

  2. The list comprehension inside the set function creates a new list with potentially n / 2 elements (in the worst-case scenario, where all elements are distinct before combining them), and then a set is created from this list. The space required for this set is proportional to the number of distinct sums, which is also up to n / 2. Hence, this gives us a space complexity of O(n).

Combining both considerations, the overall space complexity is O(n). This accounts for the space needed to store the unique sums in the worst-case scenario where all sums are distinct.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫