Count of Array elements greater than or equal to twice the Median of K trailing Array elements | C ++ Program to implement the above approach ; Function to find the count of array elements >= twice the median of K trailing array elements ; Stores frequencies ; Stores the array elements ; Count the frequencies of the array elements ; Iterating from d to n - 1 index means ( d + 1 ) th element to nth element ; To check the median ; Iterate over the frequencies of the elements ; Add the frequencies ; Check if the low_median value is obtained or not , if yes then do not change as it will be minimum ; Check if the high_median value is obtained or not , if yes then do not change it as it will be maximum ; Store 2 * median of K trailing elements ; If the current >= 2 * median ; Decrease the frequency for ( k - 1 ) - th element ; Increase the frequency of the current element ; Print the count ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int N = 2e5 ; const int V = 500 ; void solve ( int n , int d , int input [ ] ) { int a [ N ] ; int cnt [ V + 1 ] ; for ( int i = 0 ; i < n ; ++ i ) a [ i ] = input [ i ] ; int answer = 0 ; for ( int i = 0 ; i < d ; ++ i ) cnt [ a [ i ] ] ++ ; for ( int i = d ; i <= n - 1 ; ++ i ) { int acc = 0 ; int low_median = -1 , high_median = -1 ; for ( int v = 0 ; v <= V ; ++ v ) { acc += cnt [ v ] ; if ( low_median == -1 && acc >= int ( floor ( ( d + 1 ) / 2.0 ) ) ) low_median = v ; if ( high_median == -1 && acc >= int ( ceil ( ( d + 1 ) / 2.0 ) ) ) high_median = v ; } int double_median = low_median + high_median ; if ( a [ i ] >= double_median ) answer ++ ; cnt [ a [ i - d ] ] -- ; cnt [ a [ i ] ] ++ ; } cout << answer << endl ; } int main ( ) { int input [ ] = { 1 , 2 , 2 , 4 , 5 } ; int n = sizeof input / sizeof input [ 0 ] ; int k = 3 ; solve ( n , k , input ) ; return 0 ; }