Size of smallest subarray to be removed to make count of array elements greater and smaller than K equal | C ++ Program to implement the above approach ; Function ot find the length of the smallest subarray ; Stores ( prefix Sum , index ) as ( key , value ) mappings ; Iterate till N ; Update the prefixSum ; Update the length ; Put the latest index to find the minimum length ; Update the length ; Return the answer ; Function to find the length of the largest subarray ; Stores the sum of all array elements after modification ; Change greater than k to 1 ; Change smaller than k to - 1 ; Change equal to k to 0 ; Update total_sum ; No deletion required , return 0 ; Delete smallest subarray that has sum = total_sum ; Driver Code ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int smallSubarray ( int arr [ ] , int n , int total_sum ) { unordered_map < int , int > m ; int length = INT_MAX ; int prefixSum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { prefixSum += arr [ i ] ; if ( prefixSum == total_sum ) { length = min ( length , i + 1 ) ; } m [ prefixSum ] = i ; if ( m . count ( prefixSum - total_sum ) ) { length = min ( length , i - m [ prefixSum - total_sum ] ) ; } } return length ; } int smallestSubarrayremoved ( int arr [ ] , int n , int k ) { int total_sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( arr [ i ] > k ) { arr [ i ] = 1 ; } else if ( arr [ i ] < k ) { arr [ i ] = -1 ; } else { arr [ i ] = 0 ; } total_sum += arr [ i ] ; } if ( total_sum == 0 ) { return 0 ; } else { return smallSubarray ( arr , n , total_sum ) ; } } int main ( ) { int arr [ ] = { 12 , 16 , 12 , 13 , 10 } ; int K = 13 ; int n = sizeof ( arr ) / sizeof ( int ) ; cout << smallestSubarrayremoved ( arr , n , K ) ; return 0 ; }