Minimum removal of elements from end of an array required to obtain sum K | C ++ program for the above approach ; Function to find the smallest array that can be removed from the ends of an array to obtain sum K ; Sum of complete array ; If given number is greater than sum of the array ; If number is equal to the sum of array ; tar is sum of middle subarray ; Find the longest subarray with sum equal to tar ; If there is no subarray with sum equal to tar ; Driver Code ; Given Array ; Given target sum
#include <bits/stdc++.h> NEW_LINE using namespace std ; void minSizeArr ( int A [ ] , int N , int K ) { int sum = 0 ; for ( int i = 0 ; i < N ; i ++ ) sum += A [ i ] ; if ( K > sum ) { cout << -1 ; return ; } if ( K == sum ) { for ( int i = 0 ; i < N ; i ++ ) { cout << A [ i ] << " ▁ " ; } return ; } int tar = sum - K ; unordered_map < int , int > um ; um [ 0 ] = -1 ; int left , right ; int cur = 0 , maxi = -1 ; for ( int i = 0 ; i < N ; i ++ ) { cur += A [ i ] ; if ( um . find ( cur - tar ) != um . end ( ) && i - um [ cur - tar ] > maxi ) { maxi = i - um [ cur - tar ] ; right = i ; left = um [ cur - tar ] ; } if ( um . find ( cur ) == um . end ( ) ) um [ cur ] = i ; } if ( maxi == -1 ) cout << -1 ; else { for ( int i = 0 ; i <= left ; i ++ ) cout << A [ i ] << " ▁ " ; for ( int i = 0 ; i < right ; i ++ ) cout << A [ N - i - 1 ] << " ▁ " ; } } int main ( ) { int N = 7 ; int A [ ] = { 3 , 2 , 1 , 1 , 1 , 1 , 3 } ; int K = 10 ; minSizeArr ( A , N , K ) ; return 0 ; }