Find the number of sub arrays in the permutation of first N natural numbers such that their median is M | C ++ implementation of the approach ; Function to return the count of sub - arrays in the given permutation of first n natural numbers such that their median is m ; If element is less than m ; If element greater than m ; If m is found ; Count the answer ; Increment sum ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int segments ( int n , int p [ ] , int m ) { map < int , int > c ; c [ 0 ] = 1 ; bool has = false ; int sum = 0 ; long long ans = 0 ; for ( int r = 0 ; r < n ; r ++ ) { if ( p [ r ] < m ) sum -- ; else if ( p [ r ] > m ) sum ++ ; if ( p [ r ] == m ) has = true ; if ( has ) ans += c [ sum ] + c [ sum - 1 ] ; else c [ sum ] ++ ; } return ans ; } int main ( ) { int a [ ] = { 2 , 4 , 5 , 3 , 1 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; int m = 4 ; cout << segments ( n , a , m ) ; return 0 ; }