Mean of Array After Removing Some Elements

🏠 ⬅️ ➡️

Given an integer array arr, return the mean of the remaining integers after removing the smallest 5% and the largest 5% of the elements.

Answers within 10-5 of the actual answer will be considered accepted.

Example 1:

Input: arr = [1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3] Output: 2.00000 Explanation: After erasing the minimum and the maximum values of this array, all elements are equal to 2, so the mean is 2.

Example 2:

Input: arr = [6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0] Output: 4.00000

Example 3:

Input: arr = [6,0,7,0,7,5,7,8,3,4,0,7,8,1,6,8,1,1,2,4,8,1,9,5,4,3,8,5,10,8,6,6,1,0,6,10,8,2,3,4] Output: 4.77778

Constraints:

  • 20 <= arr.length <= 1000
  • arr.length is a multiple of 20.
  • 0 <= arr[i] <= 105
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: dp = selected_real_kind(15)

    integer, dimension(:), allocatable :: arr
    real(dp) :: mean

    call get_array(arr)
    call solve(arr, mean)
    write (*, '(F10.5)') mean

contains

    subroutine get_array(arr)
        implicit none
        integer, dimension(:), allocatable, intent(out) :: arr
        integer :: i, n

        read (*, *) n
        allocate (arr(n))
        do i = 1, n
            read (*, *) arr(i)
        end do
    end subroutine get_array

    subroutine solve(arr, mean)
        implicit none
        integer, dimension(:), intent(in) :: arr
        real(dp), intent(out) :: mean
        integer :: n, i, j, k, l, m, nl, nr
        real(dp) :: sum

        n = size(arr)
        if (n < 10) then
            stop "Array too small"
        end if

        ! Find the smallest 5% of the elements
        k = int(n * 0.05)
        l = 1
        m = 1
        do while (m <= k .and. l < n)
            if (arr(l) < arr(m)) then
                m = m + 1
            else
                swap(arr(l), arr(m))
                m = m + 1
            end if
            l = l + 1
        end do

        ! Find the largest 5% of the elements
        k = int(n * 0.95)
        l = n
        m = n
        do while (m >= k .and. l > 1)
            if (arr(l) > arr(m)) then
                m = m - 1
            else
                swap(arr(l), arr(m))
                m = m - 1
            end if
            l = l - 1
        end do

        ! Calculate the mean of the remaining elements
        nl = l - 1
        nr = n - m
        sum = 0.0_dp
        do i = 1, nl
            sum = sum + arr(i)
        end do
        do i = 1, nr
            sum = sum + arr(nl + i + 1)
        end do
        mean = sum / (nl + nr)
    end subroutine solve

    subroutine swap(a, b)
        implicit none
        integer, intent(inout) :: a, b
        integer :: temp

        temp = a
        a = b
        b = temp
    end subroutine swap
end program main
❌ Compiled
❌ Executed
❌ Correct 
module mean_of_remaining_integers
    implicit none
    private
    public :: mean_of_remaining_integers

contains

    subroutine mean_of_remaining_integers(arr, n, mean)
        implicit none
        integer, intent(in) :: arr(n)
        integer, intent(in) :: n
        real(kind=8), intent(out) :: mean

        integer :: i, j, k
        real(kind=8) :: sum

        ! Sort the array in ascending order
        do i = 1, n - 1
            do j = i + 1, n
                if (arr(i) > arr(j)) then
                    k = arr(i)
                    arr(i) = arr(j)
                    arr(j) = k
                end if
            end do
        end do

        ! Calculate the sum of the elements in the middle 5% of the array
        sum = 0.0d0
        i = int(0.05d0 * n) + 1
        j = int(0.95d0 * n)
        do while (i <= j)
            sum = sum + arr(i)
            i = i + 1
        end do

        ! Calculate the mean
        mean = sum / (j - i + 1)

    end subroutine mean_of_remaining_integers

end module mean_of_remaining_integers

program test_mean_of_remaining_integers
    use mean_of_remaining_integers
    implicit none
    integer, parameter :: n = 20
    integer :: arr(n) = [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3]
    real(kind=8) :: mean

    call mean_of_remaining_integers(arr, n, mean)
    write (*,*) mean

    arr = [6, 2, 7, 5, 1, 2, 0, 3, 10, 2, 5, 0, 5, 5, 0, 8, 7, 6, 8, 0]
    call mean_of_remaining_integers(arr, n, mean)
    write (*,*) mean

    arr = [6, 0, 7, 0, 7, 5, 7, 8, 3, 4, 0, 7, 8, 1, 6, 8, 1, 1, 2, 4, 8, 1, 9, 5, 4, 3, 8, 5, 10, 8, 6, 6, 1, 0, 6, 10, 8, 2, 3, 4]
    call mean_of_remaining_integers(arr, n, mean)
    write (*,*) mean

end program test_mean_of_remaining_integers
🌐 Data from online sources 
def is_path_crossing(path: str) -> bool:
    visited = {(0, 0)}
    x, y = 0, 0
    for dir in path:
        if dir == 'N': y += 1
        elif dir == 'S': y -= 1
        elif dir == 'E': x += 1
        elif dir == 'W': x -= 1
        if (x, y) in visited: return True
        visited.add((x, y))
    return False
  1. Initialize a visited set including the starting location (0,0).
  2. Iterate through each character in the path.
  3. Update the coordinates (x, y) as per the direction.
  4. Check if the updated location is already in the visited set, then return true.
  5. Add the updated location to the visited set.
  6. After iterating through the entire path return false if no crossing has occurred.
🌐 Data from online sources 
bool isPathCrossing(string path) {
    set<pair<int, int>> visited;
    int x = 0, y = 0;
    visited.insert({x, y});
    for (char dir : path) {
        if (dir == 'N') y++;
        else if (dir == 'S') y--;
        else if (dir == 'E') x++;
        else if (dir == 'W') x--;
        if (visited.count({x, y})) return true;
        visited.insert({x, y});
    }
    return false;
}
  1. Initialize a visited set including the starting location (0,0).
  2. Iterate through each character in the path.
  3. Update the coordinates (x, y) as per the direction.
  4. Check if the updated location is already in the visited set, then return true.
  5. Add the updated location to the visited set.
  6. After iterating through the entire path return false if no crossing has occurred.