- Arrays, Mathematical, Sorting

Minimum number of array indices required to be selected to make the sum of a set greater than another

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: 34 3 1Explanation: 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 = 34Output: -1Approach: 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++#include using namespace std;  void numberOfIndexes(int arr[], int brr[],                     int N, int K){        vector B;          int A = K;          for (int i = 0; i < N; i++) {                          A += arr[i];                  B.push_back({ brr[i] + 2 * arr[i], i });    }          sort(B.begin(), B.end());          reverse(B.begin(), B.end());      int tot = 0, idx = 0;          vector ans;                  while (A >= tot && idx < B.size()) {                  tot += B[idx].first;                  ans.push_back(B[idx].second);                  idx++;    }              if (tot