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++
// C++ implementation for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate// total possible different indexes// after all possible operations mentionedint 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; // Calculate 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 Codeint main(){ int N = 3; int A[] = { 2, 3, 4 }; totalFinalIndexes(A, N);} |
Java
// Java implementation for the above approachimport java.util.*;class GFG{ static class pair { int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Function to calculate// total possible different indexes// after all possible operations mentionedstatic 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<Integer> ans = new Vector<Integer>(); // Calculate the sum and push them in a // pair vector with their indices. Vector<pair > elements = new Vector<pair>(); for (int i = 0; i < N; i++) { sum += A[i]; elements.add(new pair(A[i], i)); } Collections.sort(elements,(a,b)->a.first-b.first); // 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.get(i).first; // Push the current index // in the ans vector ans.add(elements.get(i).second); // All other indexes // cannot be the possible answers if (sum < elements.get(i).first) break; } // Print the indexes of the values for (int x : ans) { System.out.print(x+ " "); } return 0;}// Driver Codepublic static void main(String[] args){ int N = 3; int A[] = { 2, 3, 4 }; totalFinalIndexes(A, N);}}// This code is contributed by shikhasingrajput |
Python3
# python implementation for the above approach# Function to calculate# total possible different indexes# after all possible operations mentioneddef totalFinalIndexes(A, N): # Variable to calculate possible indexes res = 0 # Variable to store the total sum sum = 0 # vector to store total possible indexes ans = [] # Calculate the sum and push them in a # pair vector with their indices. elements = [] for i in range(0, N): sum += A[i] elements.append([A[i], i]) elements.sort() # Iterate from right to left # and calculate total possible indexes for i in range(N-1, -1, -1): # increment the current index. res = res + 1 # Decrease the sum sum -= elements[i][0] # Push the current index # in the ans vector ans.append(elements[i][1]) # All other indexes # cannot be the possible answers if (sum < elements[i][0]): break # Print the indexes of the values for x in ans: print(x, end=" ") return 0# Driver Codeif __name__ == "__main__": N = 3 A = [2, 3, 4] totalFinalIndexes(A, N) # This code is contributed by rakeshsahni |
C#
// C# implementation for the above approachusing System;using System.Collections.Generic;public class GFG{ class pair : IComparable<pair> { public int first, second; public pair(int first, int second) { this.first = first; this.second = second; } public int CompareTo(pair p) { return this.first-p.second; } } // Function to calculate// total possible different indexes// after all possible operations mentionedstatic 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 List<int> ans = new List<int>(); // Calculate the sum and push them in a // pair vector with their indices. List<pair > elements = new List<pair>(); for (int i = 0; i < N; i++) { sum += A[i]; elements.Add(new pair(A[i], i)); } elements.Sort(); elements.Reverse(); // 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.Add(elements[i].second); // All other indexes // cannot be the possible answers if (sum < elements[i].first) break; } // Print the indexes of the values foreach (int x in ans) { Console.Write(x+ " "); } return 0;}// Driver Codepublic static void Main(String[] args){ int N = 3; int []A = { 2, 3, 4 }; totalFinalIndexes(A, N);}}// This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript implementation for the above approach // Function to calculate // total possible different indexes // after all possible operations mentioned const totalFinalIndexes = (A, N) => { // Variable to calculate possible indexes let res = 0; // Variable to store the total sum let sum = 0; // vector to store total possible indexes let ans = []; // Calculate the sum and push them in a // pair vector with their indices. let elements = []; for (let i = 0; i < N; i++) { sum += A[i]; elements.push([A[i], i]); } elements.sort((a, b) => a - b); // Iterate from right to left // and calculate total possible indexes for (let i = N - 1; i >= 0; i--) { // increment the current index. res++; // Decrease the sum sum -= elements[i][0]; // Push the current index // in the ans vector ans.push(elements[i][1]); // All other indexes // cannot be the possible answers if (sum < elements[i][0]) break; } // Print the indexes of the values for (let x in ans) { document.write(`${ans[x]} `); } return 0; } // Driver Code let N = 3; let A = [2, 3, 4]; totalFinalIndexes(A, N); // This code is contributed by rakeshsahni</script> |
Output:
2 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!
