Remove minimum elements from ends of array so that sum decreases by at least K | O ( N ) | C ++ implementation of the approach ; Function to return the count of minimum elements to be removed from the ends of the array such that the sum of the array decrease by at least K ; To store the final answer ; Maximum possible sum required ; Left point ; Right pointer ; Total current sum ; Two pointer loop ; If the sum fits ; Update the answer ; Update the total sum ; Increment the left pointer ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minCount ( int * arr , int n , int k ) { int ans = 0 ; int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) sum += arr [ i ] ; sum -= k ; int l = 0 ; int r = 0 ; int tot = 0 ; while ( l < n ) { if ( tot <= sum ) { ans = max ( ans , r - l ) ; if ( r == n ) break ; tot += arr [ r ++ ] ; } else { tot -= arr [ l ++ ] ; } } return ( n - ans ) ; } int main ( ) { int arr [ ] = { 1 , 11 , 5 , 5 } ; int n = sizeof ( arr ) / sizeof ( int ) ; int k = 11 ; cout << minCount ( arr , n , k ) ; return 0 ; }