Count of minimum reductions required to get the required sum K | C ++ Program to find the count of minimum reductions required to get the required sum K ; Function to return the count of minimum reductions ; If the sum is already less than K ; Sort in non - increasing order of difference ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countReductions ( vector < pair < int , int > > & v , int K ) { int sum = 0 ; for ( auto i : v ) { sum += i . first ; } if ( sum <= K ) { return 0 ; } sort ( v . begin ( ) , v . end ( ) , [ & ] ( pair < int , int > a , pair < int , int > b ) { return ( a . first - a . second ) > ( b . first - b . second ) ; } ) ; int i = 0 ; while ( sum > K && i < v . size ( ) ) { sum -= ( v [ i ] . first - v [ i ] . second ) ; i ++ ; } if ( sum <= K ) return i ; return -1 ; } int main ( ) { int N = 4 , K = 25 ; vector < pair < int , int > > v ( N ) ; v [ 0 ] = { 10 , 5 } ; v [ 1 ] = { 20 , 9 } ; v [ 2 ] = { 12 , 10 } ; v [ 3 ] = { 4 , 2 } ; cout << countReductions ( v , K ) << endl ; return 0 ; }