Size of smallest subarray to be removed to make count of array elements greater and smaller than K equal | Python3 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
import sys NEW_LINE def smallSubarray ( arr , n , total_sum ) : NEW_LINE INDENT m = { } NEW_LINE length = sys . maxsize NEW_LINE prefixSum = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT prefixSum += arr [ i ] NEW_LINE if ( prefixSum == total_sum ) : NEW_LINE INDENT length = min ( length , i + 1 ) NEW_LINE DEDENT m [ prefixSum ] = i NEW_LINE if ( ( prefixSum - total_sum ) in m . keys ( ) ) : NEW_LINE INDENT length = min ( length , i - m [ prefixSum - total_sum ] ) NEW_LINE DEDENT DEDENT return length NEW_LINE DEDENT def smallestSubarrayremoved ( arr , n , k ) : NEW_LINE INDENT total_sum = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( arr [ i ] > k ) : NEW_LINE INDENT arr [ i ] = 1 NEW_LINE DEDENT elif ( arr [ i ] < k ) : NEW_LINE INDENT arr [ i ] = - 1 NEW_LINE DEDENT else : NEW_LINE INDENT arr [ i ] = 0 NEW_LINE DEDENT total_sum += arr [ i ] NEW_LINE DEDENT if ( total_sum == 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT else : NEW_LINE INDENT return smallSubarray ( arr , n , total_sum ) NEW_LINE DEDENT DEDENT arr = [ 12 , 16 , 12 , 13 , 10 ] NEW_LINE K = 13 NEW_LINE n = len ( arr ) NEW_LINE print ( smallestSubarrayremoved ( arr , n , K ) ) NEW_LINE