- Arrays, Mathematical

Find the indices which will hold the Array sum after given operations

Given an array arr[], the task is to print the indices that have the highest probability of holding the entire sum of the array after performing the given operations: Choose any two elements say arr[i] and arr[j], store their sum in a variable KAssign K at index of max(arr[i], arr[j]) and assign 0 at index of min(arr[i], arr[j])In this way, after choosing all elements, the last element left will store the sum of the whole array. The task is to return the indices of the array in the sequence of the highest possibility of holding the sum of the array.Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.Examples:Input: arr[] = {2, 1, 4}Output: {2}Explanation: Choosing of elements can be done in the following ways:Way 1:Choose elements at indices {0, 1}, so arr[] = {3, 0, 4}Choose elements at indices {0, 2}, so arr[] = {0, 0, 7}Way 2:Choose elements at indices {0, 2}, so arr[] = {0, 1, 6}Choose elements at indices {1, 2}, so arr[] = {0, 0, 7}Way 3:Choose elements at indices {1, 2}, so arr[] = {2, 0, 5}Choose elements at indices {0, 2}, so arr[] = {0, 0, 7}In this case, output = {2}, index 0 and index 1 has zero possibility of holding the sum, so it is excluded.Input: arr[] = {1, 2, 4, 3}Output: {1, 2, 3}Approach: The task can be solved by sorting the given array elements, and checking if the sum till i-1th is greater than the sum till ith element or not, if it is greater, then that index has a probability to be the valid index.Take a vector of pair say v, store all the elements along with the respective indices in pair, also take a variable say sum that will store the sum of the entire array.Sort the vector in ascending order and take a counter say c, initialize with 1 because one index will always have a possibility to hold the sum of the array.Iterate over the vector from the second last element and check if the sum till the second last element is greater than the sum till the end(i.e the sum of the array), if it is greater, then increment the counter which means it has a possibility of holding the sum, else break the loop as it is not a valid index.Take a vector say ans to store the valid indices and store the indices by iterating from the end till counter, then sort the ans vector and print it.Below is the implementation of the above approach:C++#include using namespace std;  void predictIndices(int arr[], int N){        int sum = 0;              vector v;    for (int i = 0; i < N; i++) {        v.push_back({ arr[i], i });        sum += arr[i];    }          sort(v.begin(), v.end());              int c = 1;                      for (int i = N - 2; i >= 0; i–) {        sum -= v[i + 1].first;                          if (sum < v[i + 1].first) {            break;        }                else {            c++;        }    }              vector ans;                  for (int i = N - 1; i >= N – c; i–) {        ans.push_back(v[i].second);    }          sort(ans.begin(), ans.end());          for (int i = 0; i < ans.size(); i++) {        cout