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
Note: This problem is from LeetCode.
✅ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: i, j, k, n, m, min_idx, max_idx, avg
    integer, dimension(100) :: nums
    logical, dimension(100) :: used

    ! read input
    read *, n
    do i = 1, n
        read *, nums(i)
    end do

    ! solve problem
    m = 0
    do while (size(nums) > 0)
        ! find minimum
        min_idx = -1
        do i = 1, size(nums)
            if (min_idx == -1 .or. nums(i) < nums(min_idx)) then
                min_idx = i
            end if
        end do
        ! find maximum
        max_idx = -1
        do i = 1, size(nums)
            if (max_idx == -1 .or. nums(i) > nums(max_idx)) then
                max_idx = i
            end if
        end do
        ! calculate average
        avg = (nums(min_idx) + nums(max_idx)) / 2
        ! remove minimum and maximum
        used(min_idx) = .true.
        used(max_idx) = .true.
        nums(min_idx) = nums(size(nums))
        nums(max_idx) = nums(size(nums))
        nums(:) = nums(:) - 1
        ! count unique averages
        if (.not. any(used)) then
            m = m + 1
        else
            do i = 1, size(used)
                if (.not. used(i)) then
                    exit
                end if
            end do
            m = m + 1
        end if
    end do

    ! print output
    write (*, '(I0)') m

end program main
❌ Compiled
❌ Executed
❌ Correct 
module avg_of_min_max
    implicit none
    private
    public :: avg_of_min_max
contains
    function avg_of_min_max(nums) result(ans)
        integer, intent(in) :: nums(:)
        integer :: ans
        integer :: min_idx, max_idx, avg

        ans = 0
        do while (size(nums) > 0)
            min_idx = minloc(nums, 1)
            max_idx = maxloc(nums, 1)
            avg = (nums(min_idx) + nums(max_idx)) / 2
            ans = ans + 1
            nums(min_idx) = -1
            nums(max_idx) = -1
        end do
    end function avg_of_min_max
end module avg_of_min_max

program test_avg_of_min_max
    use avg_of_min_max
    implicit none
    integer, parameter :: nums1(4) = [4, 1, 4, 0, 3, 5]
    integer, parameter :: nums2(2) = [1, 100]
    integer :: ans1, ans2

    ans1 = avg_of_min_max(nums1)
    ans2 = avg_of_min_max(nums2)

    write (*,*) "Test 1:", ans1
    write (*,*) "Test 2:", ans2
end program test_avg_of_min_max
🌐 Data from online sources 
def distinctAverages(nums):
    averages = set()
    nums.sort()
    n = len(nums)
    for i in range(n // 2):
        averages.add((nums[i] + nums[n - 1 - i]) / 2.0)
    return len(averages)
  1. Initialize an empty sets called 'averages' to store the distinct averages.
  2. Sort the input array 'nums'.
  3. Iterate through the first half of the sorted array and calculate the average of the current number and its counterpart from the other end, then add this average to the 'averages' set.
  4. Return the size of the 'averages' set which represents the distinct averages calculated using the given process.
🌐 Data from online sources 
int distinctAverages(vector<int>& nums) {
    set<double> averages;
    sort(nums.begin(), nums.end());
    int n = nums.size();
    for (int i = 0; i < n / 2; i++) {
        averages.insert((nums[i] + nums[n - 1 - i]) / 2.0);
    }
    return averages.size();
}
  1. Initialize an empty sets called 'averages' to store the distinct averages.
  2. Sort the input array 'nums'.
  3. Iterate through the first half of the sorted array and calculate the average of the current number and its counterpart from the other end, then add this average to the 'averages' set.
  4. Return the size of the 'averages' set which represents the distinct averages calculated using the given process.