We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Distinct Averages

Number: 2561

Difficulty: Easy

Paid? No

Companies: Amazon

Problem Description

Given an even-length array, repeatedly remove the smallest and largest elements, compute their average, and return the number of distinct averages obtained from these operations.

Key Insights

  • Sorting the array lets us easily pair the smallest and largest elements.
  • The sorted order ensures that the smallest and largest elements are always at the opposite ends.
  • Using a set to store averages automatically handles distinct values.
  • The process continues until no elements remain in the array.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting, where n is the number of elements in the array. Space Complexity: O(n) for the sorted array copy and storage of distinct averages.

Solution

The approach involves first sorting the input array so that the smallest and largest elements are located at the beginning and end respectively. Then, use two pointers: one starting at the beginning (left pointer) and the other at the end (right pointer). In each iteration, compute the average of the numbers at the left and right pointers, store it in a set to maintain distinct averages, and move the pointers towards the center. This continues until the pointers cross. Finally, return the size of the set containing distinct averages.

Code Solutions

# Define the function to calculate distinct averages
def distinctAverages(nums):
    # Sort the array to easily access smallest and largest values
    nums.sort()
    # Initialize two pointers and an empty set to store distinct averages
    left, right = 0, len(nums) - 1
    distinct_avgs = set()
    
    # Loop until pointers meet or cross
    while left < right:
        avg = (nums[left] + nums[right]) / 2
        distinct_avgs.add(avg)
        # Move pointers inward
        left += 1
        right -= 1
    return len(distinct_avgs)

# Example usage:
print(distinctAverages([4,1,4,0,3,5]))  # Output: 2
← Back to All Questions