Given two arrays arr[] and brr[] of size N and an integer K. Consider two sets A, contains K initially, and B, initially empty. In each operation, an index is required to be selected. For every selected index, say i, arr[i] and brr[i] is added to B. For every unselected index, arr[i] is added to A. The task is to find the minimum number of indices required to be selected to make sum of B greater than sum of A. If it is not possible to do so, then print -1.
Examples:
Input: arr[] = {3, 2, 5, 6}, brr[] = {4, 4, 2, 3}, K = 12
Output: 3
4 3 1
Explanation: Indices 2, 3 and 0 are selected. Sum of B = arr[0] + brr[0] + arr[2] + brr[2] + arr[3] + brr[3] = 3 + 4 + 5 + 2 + 6 + 3 = 23. Sum of A = K + arr[1] = 12 + 2 = 14.Input: arr[] = {3, 2, 5, 6}, brr[] = {4, 4, 2, 3}, K = 34
Output: -1
Approach: The idea is to use a Greedy Approach. Follow the steps below to solve the problem:
- Initialize a vector of pair, B[] to keep track of indexes.
- Initialize a variable, A with K to store the value of set A.
- Traverse the array arr[] using the variable i,
- Add the value arr[i] to A, if the index was not chosen.
- Insert {brr[i] + 2 * arr[i], i} as a pair in vector B.
- Sort vector B in decreasing order.
- Initialize a vector, ans to store the indexes that are chosen.
- Run a while loop and keep on choosing the indices until A’s value is bigger than B.
- If all indexes are chosen but B’s value is still less than A, print “-1”.
- Otherwise, print the size of the vector ans as the minimum number of moves.
- Traverse the vector, ans, and print the chosen indices.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to print the minimum number// of indices required to be selectedvoid numberOfIndexes(int arr[], int brr[], int N, int K){ // Declare vector to keep track of indexes vector<pair<int, int> > B; // Set A contains K int A = K; // Traverse the array for (int i = 0; i < N; i++) { // Adding value that set A can // get if no index was chosen A += arr[i]; // Insert as B's value B.push_back({ brr[i] + 2 * arr[i], i }); } // Sort the vector sort(B.begin(), B.end()); // Reverse the vector reverse(B.begin(), B.end()); int tot = 0, idx = 0; // Stores chosen indexes vector<int> ans; // Keep on choosing more indices until // B's value is bigger than A or stop // incase all the indexes is chosen while (A >= tot && idx < B.size()) { // Update tot tot += B[idx].first; // Update ans ans.push_back(B[idx].second); // Increment idx idx++; } // If all indices are selected and // sum of B is less than sum of A if (tot <= A) { cout << -1 << endl; return; } // Print the minimum number of indices cout << ans.size() << endl; // Print chosen indices for (auto c : ans) cout << c + 1 << " ";}// Driver Codeint main(){ // Given arrays int arr[] = { 3, 2, 5, 6 }; int brr[] = { 4, 4, 2, 3 }; // Size of the array int N = sizeof(arr) / sizeof(arr[0]); // Given value of K int K = 12; // Function Call numberOfIndexes(arr, brr, N, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class GFG { // Function to print the minimum number // of indices required to be selected public static void numberOfIndexes(int[] arr, int[] brr, int N, int K) { // Declare list to keep track of indexes List<Pair<Integer, Integer>> B = new ArrayList<>(); // Set A contains K int A = K; // Traverse the array for (int i = 0; i < N; i++) { // Adding value that set A can // get if no index was chosen A += arr[i]; // Insert as B's value B.add(new Pair<>(brr[i] + 2 * arr[i], i)); } // Sort the list B.sort((pair1, pair2) -> pair2.getKey() - pair1.getKey()); int tot = 0, idx = 0; // Stores chosen indexes List<Integer> ans = new ArrayList<>(); // Keep on choosing more indices until // B's value is bigger than A or stop // incase all the indexes is chosen while (A >= tot && idx < B.size()) { // Update tot tot += B.get(idx).getKey(); // Update ans ans.add(B.get(idx).getValue()); // Increment idx idx++; } // If all indices are selected and // sum of B is less than sum of A if (tot <= A) { System.out.println(-1); return; } // Print the minimum number of indices System.out.println(ans.size()); // Print chosen indices for (int c : ans) { System.out.print((c + 1) + " "); } System.out.println(); } public static void main(String[] args) { // Given arrays int[] arr = {3, 2, 5, 6}; int[] brr = {4, 4, 2, 3}; // Size of the array int N = arr.length; // // Given value of K int K = 12; // Function Call numberOfIndexes(arr, brr, N, K); }}class Pair<K, V> { private K key; private V value; public Pair(K key, V value) { this.key = key; this.value = value; } public K getKey() { return key; } public V getValue() { return value; }} |
Python3
# Python 3 program for the above approach# Function to print the minimum number# of indices required to be selecteddef numberOfIndexes(arr, brr, N, K): # Declare vector to keep track of indexes B = [] # Set A contains K A = K # Traverse the array for i in range(N): # Adding value that set A can # get if no index was chosen A += arr[i] # Insert as B's value B.append([brr[i] + 2 * arr[i], i]) # Sort the vector B.sort() # Reverse the vector B = B[::-1] tot = 0 idx = 0 # Stores chosen indexes ans = [] # Keep on choosing more indices until # B's value is bigger than A or stop # incase all the indexes is chosen while (A >= tot and idx < len(B)): # Update tot tot += B[idx][0] # Update ans ans.append(B[idx][1]) # Increment idx idx += 1 # If all indices are selected and # sum of B is less than sum of A if (tot <= A): print(-1) return # Print the minimum number of indices print(len(ans)) # Print chosen indices for c in ans: print(c + 1,end = " ")# Driver Codeif __name__ == '__main__': # Given arrays arr = [3, 2, 5, 6] brr = [4, 4, 2, 3] # Size of the array N = len(arr) # Given value of K K = 12 # Function Call numberOfIndexes(arr, brr, N, K) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# code for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to print the minimum number // of indices required to be selected static void numberOfIndexes(int[] arr, int[] brr, int N, int K) { // Declare list to keep track of indexes List<Tuple<int, int>> B = new List<Tuple<int, int>>(); // Set A contains K int A = K; // Traverse the array for (int i = 0; i < N; i++) { // Adding value that set A can // get if no index was chosen A += arr[i]; // Insert as B's value B.Add(Tuple.Create(brr[i] + 2 * arr[i], i)); } // Sort the list B.Sort((pair1, pair2) => pair2.Item1 - pair1.Item1); int tot = 0, idx = 0; // Stores chosen indexes List<int> ans = new List<int>(); // Keep on choosing more indices until // B's value is bigger than A or stop // incase all the indexes is chosen while (A >= tot && idx < B.Count) { // Update tot tot += B[idx].Item1; // Update ans ans.Add(B[idx].Item2); // Increment idx idx++; } // If all indices are selected and // sum of B is less than sum of A if (tot <= A) { Console.WriteLine(-1); return; } // Print the minimum number of indices Console.WriteLine(ans.Count); // Print chosen indices foreach (int c in ans) { Console.Write((c + 1) + " "); } Console.WriteLine(); } static void Main(string[] args) { // Given arrays int[] arr = { 3, 2, 5, 6 }; int[] brr = { 4, 4, 2, 3 }; // Size of the array int N = arr.Length; // Given value of K int K = 12; // Function Call numberOfIndexes(arr, brr, N, K); }}// This code is contributed by phasing17. |
Javascript
<script>// JavaScript program for the above approach// Function to print the minimum number// of indices required to be selectedfunction numberOfIndexes(arr, brr, N, K) { // Declare vector to keep track of indexes let B = []; // Set A contains K let A = K; // Traverse the array for (let i = 0; i < N; i++) { // Adding value that set A can // get if no index was chosen A += arr[i]; // Insert as B's value B.push([brr[i] + 2 * arr[i], i]); } // Sort the vector // Reverse the vector B.sort((a, b) => a[0] - b[0]).reverse(); let tot = 0, idx = 0; // Stores chosen indexes let ans = []; // Keep on choosing more indices until // B's value is bigger than A or stop // incase all the indexes is chosen while (A >= tot && idx < B.length) { // Update tot tot += B[idx][0]; // Update ans ans.push(B[idx][1]); // Increment idx idx++; } // If all indices are selected and // sum of B is less than sum of A if (tot <= A) { document.write(-1 + "<br>"); return; } // Print the minimum number of indices document.write(ans.length + "<br>"); // Print chosen indices for (let c of ans) document.write(Number(c) + 1 + " ");}// Driver Code// Given arrayslet arr = [3, 2, 5, 6];let brr = [4, 4, 2, 3];// Size of the arraylet N = arr.length;// Given value of Klet K = 12;// Function CallnumberOfIndexes(arr, brr, N, K);</script> |
Output:
3 4 3 1
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
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!
