Find all possible unique indices after reducing the array based on given conditions

• Difficulty Level : Basic
• Last Updated : 23 Sep, 2021

Given an array arr of N integers, and an array of keys, such that key for each element in arr is equal to its index in arr initially. Given that one can perform certain moves where in one move, choose two indices (i, j), remove corresponding elements from the array, and add a new element equal to sum of the removed elements (arr[i] + arr[j]), with a key equal to the key of larger element among arr[i] and arr[j]. If both elements are equal, then any key out of the two can be used. The task is to print all possible unique keys at the end, when the array contains only a single element.

Examples: 

Input: N = 3, arr[] = {2, 3, 4}
Output: 1, 2
Explanation: Initially all elements have keys equal to their index. (2->0, 3->1, 4->2).
Case 1:

• Remove 2 and 3 and insert 5 with key 1. The new array will be (5->1, 4->2)
• Remove 5 and 4 and insert 9 with key 1. The new array will be (9->1)
• The final index in the array will be 1 for these operations.

Case 2:

• Remove 2 and 4 and insert 6 with key 2. The new array will be (3->1, 6->2)
• Remove 6 and 3 and insert 9 with key 2. The new array will be (9->2)
• The final index in the array will be 2 for these operations.

So there are a total of 2 possible unique keys (1 and 2).

 

 

 

 

Input: N = 3, arr[] = {1, 1, 4}
Output: 2 
Explanation: The final index left will be 2 in all cases. So there is a total of 1 possible index.

 

Approach: Maintain a vector of pairs which will be storing {value, i} for each arr[i] and a variable sum which will be storing the remaining sum of the left part. We sort the vector in non-decreasing order of value and start traversing from the end. Whenever the remaining sum of the left part of the array is less than the value of the current element that means all the elements in the left part cannot be the answer ever so we break the loop from here, because those elements on the left part will be at the end replaced by the keys of larger elements on the right. 

Follow the below steps as the algorithm for the above approach:

• Maintain a pair vector that stores the elements of the array in the form of {value, index}
• Sort the pair vector in non-decreasing order of value.
• Take a variable sum which will be initially storing the sum of all the elements in the array.
• Iterate from right to left in the sorted vector.
• If the value of the current element is greater than the sum of all elements in its left then break the loop, otherwise, add the current index as a valid answer and decrease the sum by the value of the current element and continue for the remaining elements.
• At the end return all possible indices in the answer.

Below is the implementation of the above approach: 

• C++
• Java
• Python3
• C#
• Javascript

// C++ implementation for the above approach

#include <bits/stdc++.h>

using namespace std;

// Function to calculate

// total possible different indexes

// after all possible operations mentioned

int totalFinalIndexes(int A[], int N)

{

    // Variable to calculate possible indexes

    int res = 0;

    // Variable to store the total sum

    int sum = 0;

    // vector to store total possible indexes

    vector<int> ans;

    // Calculat the sum and push them in a

    // pair vector with their indices.

    vector<pair<int, int> > elements;

    for (int i = 0; i < N; i++) {

        sum += A[i];

        elements.push_back(make_pair(A[i], i));

    }

    sort(elements.begin(), elements.end());

    // Iterate from right to left

    // and calculate total possible indexes

    for (int i = N - 1; i >= 0; i--) {

        // increment the current index.

        res++;

        // Decrease the sum

        sum -= elements[i].first;

        // Push the current index

        // in the ans vector

        ans.push_back(elements[i].second);

        // All other indexes

        // cannot be the possible answers

        if (sum < elements[i].first)

            break;

    }

    // Print the indexes of the values

    for (auto x : ans) {

        cout << x << " ";

    }

    return 0;

}

// Driver Code

int main()

{

    int N = 3;

    int A[] = { 2, 3, 4 };

    totalFinalIndexes(A, N);

}

Output: 

2 1

Time Complexity: O(N*log(N)) 
Auxiliary Space: O(N)