Compute the subarray of length K whose mean exceeds the median of the given array

The expression "K length subarray" applies to a contiguous subarray with exactly K elements. Mastering and using subarrays is essential for solving a variety of problems in areas such as dynamic programming, computational geometry, and data analysis.

Another important concept in array operations and statistics is the median. The median of an array represents the value in the middle when the elements are sorted in ascending order. When there is an even number of elements, the median is the average of the two central values. The median constitutes a persistent measure of central tendency because it is less susceptible to extreme values ​​or outliers than the mean.

This article attempts to study the challenge of determining the number of K-length subarrays in a given array whose mean exceeds the median. By understanding the relationship between the mean and median of a data set, we can delve into this challenge and develop efficient techniques to solve it. Join us as we dissect the problem statement, examine key concepts, and algorithmically efficiently calculate the number of K-length subarrays required in an array.

grammar

Sort the elements in the array in ascending order.

sort(begin(array), end(array))

Declare an integer vector.

vector<int> vec
</int>

Declare an integer array

int arr[]

Basic for loop syntax in C.

for(int i=0; i<size; ++i)

Source code algorithm

• Read the input array and its size.

• Calculate the median of the given array.

• For each subarray of length K, calculate the average.

• Compare the mean to the median.

• Statistics subarrays whose average value exceeds the median.

Method 1: Brute force cracking

Method 1 constitutes a simple solution to the challenge of determining the number of K-length subarrays whose mean exceeds the median of a specified array. Initially, the input array is sorted and the median is calculated. Subsequently, the program iterates through all feasible K-length subarrays and calculates their average by aggregating their components. If the mean of the subarray exceeds the median, the count is incremented. Finally, the code returns the number of such subarrays.

algorithm

• Calculate the median of the given array.

• Iterate over all possible K-length subarrays.

• Calculate the average of each subarray.

• If the mean of the subarray is greater than the median, increment the count.

Example 1

The code below follows the brute force approach mentioned earlier in this article. It first sorts the input array and calculates the median. It then iterates over all possible K length subarrays and calculates their average by summing their elements. If the mean of the subarray is greater than the median, the count is incremented. Finally, the code returns the count of such subarrays.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int countSubarrays(vector<int> &arr, int n, int k) {
   int count = 0;
   double median;
   sort(arr.begin(), arr.end());
   median = (n % 2 == 0) ? (arr[n/2 - 1] + arr[n/2]) / 2.0 : arr[n/2];

   for (int i = 0; i <= n - k; i++) {
      double sum = 0;
      for (int j = i; j < i + k; j++) {
         sum += arr[j];
      }
      if (sum / k > median) {
         count++;
      }
   }
   return count;
}

int main() {
   vector<int> arr = {1, 5, 6, 7, 9};
   int n = arr.size();
   int k = 3;
   int result = countSubarrays(arr, n, k);
   cout << "Number of K-length subarrays with average exceeding median: " << result << endl;
   return 0;
}

Output

Number of K-length subarrays with average exceeding median: 1

Method 2: Optimization method

Method 2 is an elegant solution to the problem of determining the number of K-length subarrays with a mean exceeding the median of a specified array. It first sorts the input array and calculates the median. It then computes the prefix sum array, which is used to determine the sum of each K-length subarray. The algorithm iterates over all possible subarrays of K length, calculates their average using the prefix sum array, and compares with the median.

If the mean of the subarray exceeds the median, the count is incremented. Finally, the program returns the number of such subarrays. This approach is more efficient than the first approach because it utilizes a prefix sum array to compute the sum of each K-length subarray, thus reducing the runtime complexity.

algorithm

• Calculate the median of the given array.

• Calculate prefix sum array.

• Iterate over all possible K-length subarrays.

• Calculate the average using prefix and array.

• If the mean of the subarray is greater than the median, increment the count.

Example 2

The algorithm follows the best approach described previously. It leverages prefix sum arrays to quickly compute aggregates for each K-length subset. After the input sequence is sorted and the median value is determined, the prefix sum is calculated. The program then loops over all K-length subsets, calculates their average using the prefix sum array, and compares it to the median. If the mean exceeds the median, the count is incremented. In summary, the code returns the number of such subsets.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int countSubarrays(vector<int> &arr, int n, int k) {
   int count = 0;
   double median;
   sort(arr.begin(), arr.end());
   median = (n % 2 == 0) ? (arr[n/2 - 1] + arr[n/2]) / 2.0 : arr[n/2];

   vector<int> prefix_sum(n);
   prefix_sum[0] = arr[0];
   for (int i = 1; i < n; i++) {
      prefix_sum[i] = prefix_sum[i - 1] + arr[i];
   }

   for (int i = 0; i <= n - k; i++) {
      double sum = (i == 0) ? prefix_sum[i + k - 1] : prefix_sum[i + k - 1] - prefix_sum[i - 1];
      if (sum / k > median) {
         count++;
      }
   }
   return count;
}

int main() {
   vector<int> arr = {1, 5, 6, 7, 9};
   int n = arr.size();
   int k = 3;
   int result = countSubarrays(arr, n, k);
   cout << "Number of K-length subarrays with average exceeding median: " << result << endl;
   return 0;
}

Output

Number of K-length subarrays with average exceeding median: 1

in conclusion

In this article, we discussed two methods using C to calculate K-length subarrays whose mean exceeds the median of a given array. The first method is the brute force method, which iterates over all possible K length subarrays and calculates their average. The second method is an optimization method that uses prefixes and arrays to calculate the average more efficiently. Both codes are provided and can be executed to find the required number of subarrays.

The above is the detailed content of Compute the subarray of length K whose mean exceeds the median of the given array. For more information, please follow other related articles on the PHP Chinese website!