Given two arrays A[] and B[] of N integers, the task is to find for each element A[i], the size of the smallest subset S of indices, such that :
- Each value corresponding to the indices in subset S is strictly less than A[i].
- Sum of elements corresponding to the indices in B is strictly greater than B[i].
Examples:
Input: N = 5, A = {3, 2, 100, 4, 5}, B = {1, 2, 3, 4, 5}
Output: {1, -1, 1, -1, 3}
Explanation: Subsets for each element of A are :
A[0] : {1}, (A[1] < A[0] and B[1] > B[0])
A[1] : {}, (no such subset exist )
A[2] : {4}, (A[4] < A[2] and B[4] > B[2])
A[3] : {}, (no such subset exist )
A[4] : {0, 1, 3}, (A[0] < A[4], A[1] < A[4], A[3] < A[4] and (B[0]+B[1]+B[3] > B[4]) )Input : N = 4, A = {1, 1, 1, 1}, B = {2, 4, 5, 9}
Output : {-1, -1, -1, -1}
Approach: The problem can be solved by a greedy approach using a multiset as per the following idea:
Sort the array A[] along with their indices and for each element in sorted array find the smallest subset having elements of B with sum greater than current element of B.
Use multiset in decreasing order to store elements of B.
Follow the below steps to solve this problem:
- Declare a vector v of pairs, that stores the elements of array A along with their indices.
- Sort the vector v. After sorting, the 1st condition is fulfilled for each element.
- Declare a multiset s so that elements in multiset are in decreasing order.
- Iterate through the vector v and at each ith iteration:
- Store the element in array B corresponding to the index in ith element of vector (i.e. 2nd element of pair) in a variable say curr_B.
- Iterate through the set, simultaneously keeping the count and sum of elements of the set, until the sum becomes just greater than curr_B.
- Insert curr_B into the set and count ( of the required set ) found for ith element into array storing answer (ans).
- Return the ans vector after the completion of all iteration.
Below is the implementation of the above approach :
C++
// C++ program for Find minimum size of subset// for each index of the array satisfying the// given condition#include <bits/stdc++.h>using namespace std;// Functions to print minimum size of subset// for each element satisfying the given conditionsvoid printSubsets(int N, int A[], int B[]){ // storing the elements of A along with // their indices in a vector of pairs v vector<pair<int, int> > v(N); for (int i = 0; i < N; i++) { v[i] = { A[i], i }; } // sorting the vector v sort(v.begin(), v.end()); // declaring a vector of size N to // store the answer vector<int> ans(N); // declaring a multiset to store the // corresponding values of B multiset<int, greater<int> > s; // iterating through the sorted vector v. // Since the vector is sorted, so the 1st // condition is already fulfilled, i.e. // all the elements of A at indices of resultant // set would be less than current A[i] for (int i = 0; i < N; i++) { int curr_B = B[v[i].second]; int size = 0; int sum = 0; // iterating through the set to find // the minimum set whose sum>B[i] //(or curr_B) for (auto x : s) { sum += x; size += 1; if (sum > curr_B) break; } // inserting the current element of B // into the set s.insert(curr_B); // if sum>B[i] condition is fulfilled, // we assign size of resultant subset to // the answer at the index if (sum > curr_B) { ans[v[i].second] = size; } // else we assign -1 else { ans[v[i].second] = -1; } } // printing the answer for (int i = 0; i < N; i++) { cout << ans[i] << " "; }}// Driver Codeint main(){ int N = 5; int A[] = { 3, 2, 100, 4, 5 }; int B[] = { 1, 2, 4, 3, 5 }; printSubsets(N, A, B);} |
Java
import java.util.*;import java.io.*;// Java program for Find minimum size of subset// for each index of the array satisfying the// given conditionpublic class GFG{ // Functions to print minimum size of subset // for each element satisfying the given conditions public static void printSubsets(int N, int A[], int B[]){ // Storing the elements of A along with // their indices in a arrayList of pairs v Pair v[] = new Pair[N]; for(int i = 0 ; i < N ; i++){ v[i] = new Pair(A[i], i); } // Sorting the array v Arrays.sort(v, new comp()); // Declaring a array of size N to // store the answer int ans[] = new int[N]; // Declaring a map to store the corresponding // values of B TreeMap<Integer, Integer> s = new TreeMap<Integer,Integer>(); // iterating through the sorted arraylist v. // Since the arraylist is sorted, so the 1st // condition is already fulfilled, i.e. // all the elements of A at indices of resultant // set would be less than current A[i] for (int i = 0 ; i < N ; i++) { int curr_B = B[v[i].second]; int size = 0; int sum = 0; // iterating through the set to find // the minimum set whose sum>B[i] //(or curr_B) for (Map.Entry<Integer, Integer> x : s.entrySet()) { for(int j=1 ; j<=x.getValue() ; j++){ sum += (-x.getKey()); size += 1; if (sum > curr_B) break; } if (sum > curr_B) break; } // inserting the current element of B // into the TreeMap if(s.containsKey(-curr_B)){ s.put(-curr_B, s.get(-curr_B)+1); }else{ s.put(-curr_B, 1); } // if sum>B[i] condition is fulfilled, // we assign size of resultant subset to // the answer at the index if (sum > curr_B) { ans[v[i].second] = size; } // else we assign -1 else { ans[v[i].second] = -1; } } // printing the answer for (int i = 0; i < N; i++) { System.out.print(ans[i] + " "); } } // Driver code public static void main(String args[]) { int N = 5; int A[] = {3, 2, 100, 4, 5}; int B[] = {1, 2, 4, 3, 5}; printSubsets(N, A, B); }}class Pair{ Integer first; Integer second; Pair(int x, int y){ this.first = x; this.second = y; }}class comp implements Comparator<Pair>{ public int compare(Pair x, Pair y){ if(x.first.equals(y.first)){ return x.second.compareTo(y.second); } return x.first.compareTo(y.first); }}// This code is contributed by subhamgoyal2014. |
Python3
# Python program to find the minimum size of the subset# for each index of the array satisfying the given conditionimport bisect#Functions to print minimum size of subset#for each element satisfying the given conditionsdef printSubsets(N, A, B): #storing the elements of A along with #their indices in a vector of pairs v v = [[A[i], i] for i in range(N)] v.sort() #sorting v #initializing ans, s ans = [0] * N s = list() for i in range(N): curr_B = B[v[i][1]] size = 0 sums = 0 for ele in s: sums += ele size += 1 if sums > curr_B: break #to ensure that sorted status of s is maintained bisect.insort(s, curr_B) if (sums > curr_B): ans[v[i][1]] = size else: ans[v[i][1]] = -1 print(" ".join(list(map(str, ans))))# Driver CodeN = 5A = [3, 2, 100, 4, 5]B = [1, 2, 4, 3, 5]printSubsets(N, A, B)# This code is contributed by phalasi. |
Javascript
<script>// JS program for Find minimum size of subset// for each index of the array satisfying the// given condition// Functions to print minimum size of subset// for each element satisfying the given conditionsfunction printSubsets(N, A, B){ // storing the elements of A along with // their indices in a vector of pairs v var v = []; for (var i = 0; i < N; i++) { v.push([ A[i], i ]); } // sorting the vector v v.sort(); // declaring a vector of size N to // store the answer var ans = new Array(N).fill(0); // declaring a multiset to store the // corresponding values of B var s = []; // iterating through the sorted vector v. // Since the vector is sorted, so the 1st // condition is already fulfilled, i.e. // all the elements of A at indices of resultant // set would be less than current A[i] for (var i = 0; i < N; i++) { var curr_B = B[v[i][1]]; var size = 0; var sum = 0; // iterating through the set to find // the minimum set whose sum>B[i] //(or curr_B) for (var j = 0; j < s.length; j++) { sum += s[j]; size += 1; if (sum > curr_B) break; } // inserting the current element of B // into the sorted list s // this implementation mimics // C++ multiset or Python insort. var ind = 0; for (var j = 0; j < s.length; j++) { if (s[j] > curr_B) break; ind++; } s.splice(ind, 0, curr_B); // if sum>B[i] condition is fulfilled, // we assign size of resultant subset to // the answer at the index if (sum > curr_B) { ans[v[i][1]] = size; } // else we assign -1 else { ans[v[i][1]] = -1; } } // printing the answer for (var i = 0; i < N; i++) { document.write(ans[i] + " "); }}// Driver Codevar N = 5;var A = [ 3, 2, 100, 4, 5 ];var B = [ 1, 2, 4, 3, 5 ];printSubsets(N, A, B);// This code is contributed by phasing17.</script> |
C#
using System;using System.Linq;using System.Collections.Generic;// C# program for Find minimum size of subset// for each index of the array satisfying the// given conditionclass GFG { static void PrintSubsets(int N, int[] A, int[] B) { List<(int, int)> v = new List<(int, int)>(); for (int i = 0; i < N; i++) { v.Add((A[i], i)); } v.Sort(); int[] ans = new int[N]; SortedSet<int> s = new SortedSet<int>(); for (int i = 0; i < N; i++) { int curr_B = B[v[i].Item2]; int size = 0; int sum = 0; foreach(var x in s) { sum += x; size += 1; if (sum > curr_B) break; } s.Add(curr_B); if (sum > curr_B) { ans[v[i].Item2] = size; } else { ans[v[i].Item2] = -1; } } for (int i = 0; i < N; i++) { Console.Write(ans[i] + " "); } } static void Main() { int N = 5; int[] A = { 3, 2, 100, 4, 5 }; int[] B = { 1, 2, 4, 3, 5 }; PrintSubsets(N, A, B); }} |
Output
1 -1 1 -1 3
Time Complexity : O(N^2)
Auxiliary Space : O(N)
