Finden Sie alle möglichen eindeutigen Indizes, nachdem Sie das Array basierend auf gegebenen Bedingungen reduziert haben
Bei einem Array arr von N ganzen Zahlen und einem Array von Schlüsseln, so dass der Schlüssel für jedes Element in arr anfänglich gleich seinem Index in arr ist. Da man bestimmte Züge ausführen kann, wobei man in einem Zug zwei Indizes (i, j) auswählt, entsprechende Elemente aus dem Array entfernt und ein neues Element gleich der Summe der entfernten Elemente hinzufügt ( arr [i] + arr [j] ), mit einem Schlüssel gleich dem Schlüssel des größeren Elements zwischen arr[i] und arr[j]. Wenn beide Elemente gleich sind, kann jeder Schlüssel aus den beiden verwendet werden. Die Aufgabe besteht darin, alle möglichen eindeutigen Schlüssel am Ende auszugeben, wenn das Array nur ein einziges Element enthält.
Beispiele:
Eingabe: N = 3, arr[] = {2, 3, 4}
Ausgabe: 1, 2
Erläuterung: Anfangs haben alle Elemente Schlüssel gleich ihrem Index. (2->0, 3->1, 4->2).
Fall 1:
- Entfernen Sie 2 und 3 und fügen Sie 5 mit Schlüssel 1 ein. Das neue Array ist (5->1, 4->2)
- Entfernen Sie 5 und 4 und fügen Sie 9 mit Schlüssel 1 ein. Das neue Array ist (9->1)
- Der letzte Index im Array ist für diese Operationen 1.
Fall 2:
- Entfernen Sie 2 und 4 und fügen Sie 6 mit Schlüssel 2 ein. Das neue Array ist (3->1, 6->2)
- Entfernen Sie 6 und 3 und fügen Sie 9 mit Schlüssel 2 ein. Das neue Array ist (9->2)
- Der letzte Index im Array ist für diese Operationen 2.
Es gibt also insgesamt 2 mögliche eindeutige Schlüssel (1 und 2).
Eingabe: N = 3, arr[] = {1, 1, 4}
Ausgabe: 2
Erläuterung: Der letzte verbleibende Index ist in allen Fällen 2. Es gibt also insgesamt 1 möglichen Index.
Ansatz: Pflegen Sie einen Vektor von Paaren, der {Wert, i} für jedes arr[i] und eine variable Summe ergibt, die die verbleibende Summe des linken Teils speichert. Wir sortieren den Vektor in nicht absteigender Wertreihenfolge und beginnen mit der Traversierung am Ende. Immer wenn die verbleibende Summe des linken Teils des Arrays kleiner als der Wert des aktuellen Elements ist, bedeutet dies, dass nicht alle Elemente im linken Teil die Antwort sein können, also brechen wir die Schleife von hier ab, weil die Elemente im linken Teil es sein werden am Ende ersetzt durch die Tasten größerer Elemente auf der rechten Seite.
Befolgen Sie die folgenden Schritte als Algorithmus für den obigen Ansatz:
- Pflegen Sie einen Paarvektor , der die Elemente des Arrays in Form von {Wert, Index} speichert
- Sortieren Sie den Paarvektor in nicht absteigender Wertreihenfolge.
- Nehmen Sie eine variable Summe , die anfänglich die Summe aller Elemente im Array speichert.
- Im sortierten Vektor von rechts nach links iterieren .
- Wenn der Wert des aktuellen Elements größer als die Summe aller Elemente auf der linken Seite ist, unterbrechen Sie die Schleife. Andernfalls fügen Sie den aktuellen Index als gültige Antwort hinzu und verringern Sie die Summe um den Wert des aktuellen Elements und fahren Sie mit den verbleibenden Elementen fort .
- Geben Sie am Ende alle möglichen Indizes in der Antwort zurück.
Unten ist die Implementierung des obigen Ansatzes:
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 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);
}
Java
// Java implementation for the above approach
import 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 mentioned
static 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>();
// Calculat 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 Code
public 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 mentioned def 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 = [] # Calculat 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 Code if __name__ == "__main__": N = 3 A = [2, 3, 4] totalFinalIndexes(A, N) # This code is contributed by rakeshsahni
C#
// C# implementation for the above approach
using 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 mentioned
static 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>();
// Calculat 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 Code
public 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 = [];
// Calculat 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>
2 1
Zeitkomplexität: O(N*log(N))
Hilfsraum: O(N)
Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .