Number of Distinct Averages - Practice Coding Problems

Number of Distinct Averages - 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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [4,1,4,0,3,5]

› Output: 2

💡 Note: Removing pairs: (0,5)→avg=2.5, (1,4)→avg=2.5, (3,4)→avg=3.5. Distinct averages: {2.5, 3.5}, so return 2

Example 2 — All Same Average

$ Input: nums = [1,100]

› Output: 1

💡 Note: Only one pair possible: (1,100)→avg=50.5. Only one distinct average, so return 1

Example 3 — Multiple Duplicates

$ Input: nums = [1,2,3,1,2,3]

› Output: 1

💡 Note: After sorting [1,1,2,2,3,3]: pairs (1,3)→avg=2, (1,3)→avg=2, (2,2)→avg=2. All same average, return 1

Constraints

2 ≤ nums.length ≤ 100
nums.length is even
0 ≤ nums[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Array of even length integers

Process

Repeatedly remove min/max pairs and calculate averages

Output

Count of distinct averages

Key Takeaway

🎯 Key Insight: Sorting allows us to efficiently pair minimum and maximum elements using two pointers

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that after sorting, we can use two pointers to efficiently pair minimum and maximum elements. The optimal approach sorts the array once, then uses two pointers moving inward to calculate averages. Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Repeated Min/Max Finding	O(n²)	O(n)	Find min/max in array repeatedly until empty
Two Pointers on Sorted Array	O(n log n)	O(n)	Sort array once, then use two pointers from ends

Brute Force - Repeated Min/Max Finding — Algorithm Steps

While array is not empty
Find minimum and maximum elements
Remove both elements from array
Calculate average and add to set
Return size of set

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Min/Max

Scan entire array to find minimum and maximum

Remove & Calculate

Remove both values and calculate their average

Repeat

Continue until array is empty

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int* nums, int size) {
    double averages[1000]; // Assume max 1000 distinct averages
    int avgCount = 0;
    
    while (size > 0) {
        int minVal = INT_MAX, maxVal = INT_MIN;
        int minIdx = -1, maxIdx = -1;
        
        // Find min and max
        for (int i = 0; i < size; i++) {
            if (nums[i] < minVal) {
                minVal = nums[i];
                minIdx = i;
            }
            if (nums[i] > maxVal) {
                maxVal = nums[i];
                maxIdx = i;
            }
        }
        
        // Calculate average
        double avg = (minVal + maxVal) / 2.0;
        
        // Check if average already exists
        int found = 0;
        for (int i = 0; i < avgCount; i++) {
            if (averages[i] == avg) {
                found = 1;
                break;
            }
        }
        if (!found) {
            averages[avgCount++] = avg;
        }
        
        // Remove elements (remove higher index first)
        if (minIdx > maxIdx) {
            for (int i = minIdx; i < size - 1; i++) nums[i] = nums[i + 1];
            size--;
            for (int i = maxIdx; i < size - 1; i++) nums[i] = nums[i + 1];
            size--;
        } else if (maxIdx > minIdx) {
            for (int i = maxIdx; i < size - 1; i++) nums[i] = nums[i + 1];
            size--;
            for (int i = minIdx; i < size - 1; i++) nums[i] = nums[i + 1];
            size--;
        } else {
            // Same element, remove it twice
            for (int i = minIdx; i < size - 1; i++) nums[i] = nums[i + 1];
            size--;
            for (int i = 0; i < size; i++) {
                if (nums[i] == maxVal) {
                    for (int j = i; j < size - 1; j++) nums[j] = nums[j + 1];
                    size--;
                    break;
                }
            }
        }
    }
    
    return avgCount;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int size = 0;
    
    // Parse JSON array
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int num = atoi(token);
        nums[size++] = num;
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n/2 pairs, we scan the remaining array to find min/max

⚠ Quadratic Growth

Space Complexity

O(n)

Set stores up to n/2 distinct averages

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~15 min Avg. Time

487 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Repeated Min/Max Finding — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler