Minimum array elements required to be subtracted from either end to reduce K to 0 | C ++ program for the above approach ; Function to find the length of longest subarray having sum K ; Stores the index of the prefix sum ; Traverse the given array ; Update sum ; If the subarray starts from index 0 ; Add the current prefix sum with index if it is not present in the map um ; Check if sum - K is present in Map um or not ; Update the maxLength ; Return the required maximum length ; Function to find the minimum removal of array elements required to reduce K to 0 ; Stores the sum of the array ; Traverse the array arr [ ] ; Update sum of the array ; Find maxLen ; If the subarray with sum doesn 't exist ; Otherwise , print the required maximum length ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int longestSubarray ( int arr [ ] , int N , int K ) { unordered_map < int , int > um ; int sum = 0 , maxLen = 0 ; for ( int i = 0 ; i < N ; i ++ ) { sum += arr [ i ] ; if ( sum == K ) maxLen = i + 1 ; if ( um . find ( sum ) == um . end ( ) ) um [ sum ] = i ; if ( um . find ( sum - K ) != um . end ( ) ) { if ( maxLen < ( i - um [ sum - K ] ) ) maxLen = i - um [ sum - K ] ; } } return maxLen ; } void minRequiredOperation ( int arr [ ] , int N , int K ) { int TotalSum = 0 ; for ( int i = 0 ; i < N ; i ++ ) TotalSum += arr [ i ] ; int maxLen = longestSubarray ( arr , N , TotalSum - K ) ; if ( maxLen == -1 ) { cout << -1 ; } else cout << N - maxLen ; } int main ( ) { int arr [ ] = { 1 , 3 , 1 , 1 , 2 } ; int K = 4 ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; minRequiredOperation ( arr , N , K ) ; return 0 ; }