Given N pairs of integers and an integer K, the task is to find the minimum number of reductions required such that the sum of the first elements of each pair is ? K.Each reduction involves reducing the first value of a pair to its second value. If it is not possible to make the sum ? K, print -1.
Examples:
Input: N = 5, K = 32
10 6
6 4
8 5
9 8
5 2
Output: 2
Explanation:
Total Sum = 10 + 6 + 8 + 9 + 5 = 38 > K
Reducing 10 – > 6 and 8 – > 5 reduces the sum to 31( 6 + 6 + 5 + 9 + 5) which is less than K.Input: N = 4, K = 25
10 5
20 9
12 10
4 2
Output: -1
Approach:
Follow the steps below to solve the problem:
- Calculate the sum of the first element of every pair. If the sum is already ? K, print 0.
- Sort the given pairs based on their difference.
- Count the number of differences of pairs that need to be added in non-increasing order to get the sum to be less than K.
- If the sum exceeds K after traversal of all pairs, print -1. Otherwise, print the count.
Below is the implementation of the above approach:
C++
// C++ Program to find the count of// minimum reductions required to// get the required sum K#include <bits/stdc++.h>using namespace std;// Function to return the count// of minimum reductionsint countReductions( vector<pair<int, int> >& v, int K){ int sum = 0; for (auto i : v) { sum += i.first; } // If the sum is already // less than K if (sum <= K) { return 0; } // Sort in non-increasing // order of difference 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;}// Driver Codeint 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 }; // Function Call cout << countReductions(v, K) << endl; return 0;} |
Java
// Java program to find the count of // minimum reductions required to // get the required sum K import java.util.*;class GFG{ // Function to return the count// of minimum reductionsstatic int countReductions(ArrayList<int[]> v, int K){ int sum = 0; for(int[] i : v) { sum += i[0]; } // If the sum is already // less than K if (sum <= K) { return 0; } // Sort in non-increasing // order of difference Collections.sort(v, (a, b) -> Math.abs(b[0] - b[1]) - Math.abs(a[0] - a[1])); int i = 0; while (sum > K && i < v.size()) { sum -= (v.get(i)[0] - v.get(i)[1]); i++; } if (sum <= K) return i; return -1;}// Driver codepublic static void main(String[] args){ int N = 4, K = 25; ArrayList<int[]> v = new ArrayList<>(); v.add(new int[] { 10, 5 }); v.add(new int[] { 20, 9 }); v.add(new int[] { 12, 10 }); v.add(new int[] { 4, 2 }); // Function Call System.out.println(countReductions(v, K));}}// This code is contributed by offbeat |
Python3
# Python3 program to find the count of# minimum reductions required to# get the required sum Kfrom typing import Any, List# Function to return the count# of minimum reductionsdef countReductions(v: List[Any], K: int) -> int: sum = 0 for i in v: sum += i[0] # If the sum is already # less than K if (sum <= K): return 0 # Sort in non-increasing # order of difference v.sort(key = lambda a : a[0] - a[1]) i = 0 while (sum > K and i < len(v)): sum -= (v[i][0] - v[i][1]) i += 1 if (sum <= K): return i return -1# Driver Codeif __name__ == "__main__": N = 4 K = 25 v = [[0, 0] for _ in range(N)] v[0] = [10, 5] v[1] = [20, 9] v[2] = [12, 10] v[3] = [4, 2] # Function Call print(countReductions(v, K))# This code is contributed by sanjeev2552 |
C#
// C# program to find the count of// minimum reductions required to// get the required sum Kusing System;using System.Linq;using System.Collections.Generic;class GFG { // Function to return the count // of minimum reductions static int countReductions(List<int[]> v, int K) { int sum = 0; foreach(var j in v) { sum += j[0]; } // If the sum is already // less than K if (sum <= K) { return 0; } // Sort in non-increasing // order of difference v = v.OrderBy(b => Math.Abs(b[0] - b[1])).ToList(); int i = 0; while (sum > K && i < v.Count) { sum -= (v[i][0] - v[i][1]); i++; } if (sum <= K) return i; return -1; } // Driver code public static void Main(string[] args) { int K = 25; List<int[]> v = new List<int[]>(); v.Add(new[] { 10, 5 }); v.Add(new[] { 20, 9 }); v.Add(new[] { 12, 10 }); v.Add(new[] { 4, 2 }); // Function Call Console.WriteLine(countReductions(v, K)); }}// This code is contributed by phasing17 |
Javascript
// JS program to find the count of// minimum reductions required to// get the required sum K// Function to return the count// of minimum reductionsfunction countReductions(v, K){ let sum = 0 for (let i of v) sum += i[0] // If the sum is already // less than K if (sum <= K) return 0 // Sort in non-increasing // order of difference v.sort(function (a) { return a[0] - a[1]}) let i = 0 while (sum > K && i < v.length) { sum -= (v[i][0] - v[i][1]) i += 1 } if (sum <= K) return i return -1}// Driver Codelet N = 4let K = 25let v = []for (var i = 0; i < N; i++) v.push([0, 0]) v[0] = [10, 5]v[1] = [20, 9]v[2] = [12, 10]v[3] = [4, 2]// Function Callconsole.log(countReductions(v, K))// This code is contributed by phasing17 |
Output:
-1
Time Complexity:O(NlogN)
Auxiliary Space:O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
