Dada una array A[] de enteros. La tarea es imprimir todos los índices 
de esta array de manera que después de eliminar el i- ésimo elemento de la array, la array se convierta en una buena array .
Nota :
- Una array es buena si hay un elemento en la array que es igual a la suma de todos los demás elementos.
- La indexación basada en 1 se considera para la array.
Ejemplos :
Entrada : A[] = { 8, 3, 5, 2 }
Salida : 1 4
Explicación : A[] = [8, 3, 5, 2]
Si elimina A[1], la array se verá como [3, 5, 2] y es bueno, ya que 5 = 3+2.
Si elimina A[4], la array se verá como [8, 3, 5] y está bien, ya que 8 = 3+5.
Por lo tanto, los buenos índices son 1 y 4.
Entrada : A[] = { 2, 2, 2 }
Salida : 1 2 3
Eliminar cualquier elemento en cualquier índice hará que la array sea buena.
Acercarse:
- Cree un hash de la array A[] que almacene la frecuencia de cada elemento y una suma variable que tenga la suma de cada elemento de A.
- Itere la array, elimine el elemento en el índice i para cada uno
. - Después de eliminar un elemento, la suma de la array restante es K, donde K = sum – A[i].
- Tenemos que encontrar un elemento K/2 en la array restante para hacerlo bien. Sea K = K/2 por ahora.
- Ahora, la array restante será buena si y solo si las condiciones a continuación son ciertas.
- Si A[i] == K y hash(K) > 1 O Si A[i] != K y hash(K) > 0.
- Imprimir todos esos índices i.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find all good indices
// in the given array
#include <bits/stdc++.h>
using namespace std;
// Function to find all good indices
// in the given array
void niceIndices(int A[], int n)
{
int sum = 0;
// hash to store frequency
// of each element
map<int, int> m;
// Storing frequency of each element
// and calculating sum simultaneously
for (int i = 0; i < n; ++i) {
m[A[i]]++;
sum += A[i];
}
for (int i = 0; i < n; ++i) {
int k = sum - A[i];
if (k % 2 == 0) {
k = k >> 1;
// check if array is good after
// removing i-th index element
if (m.find(k) != m.end()) {
if ((A[i] == k && m[k] > 1) || (A[i] != k))
// print good indices
cout << (i + 1) << " ";
}
}
}
}
// Driver Code
int main()
{
int A[] = { 8, 3, 5, 2 };
int n = sizeof(A) / sizeof(A[0]);
niceIndices(A, n);
return 0;
}
Java
// Java program to find all good indices
// in the given array
import java.util.*;
class Solution
{
// Function to find all good indices
// in the given array
static void niceIndices(int A[], int n)
{
int sum = 0;
// hash to store frequency
// of each element
Map<Integer, Integer> m=new HashMap<Integer, Integer>();
// Storing frequency of each element
// and calculating sum simultaneously
for (int i = 0; i < n; ++i) {
m.put(A[i],(m.get(A[i])==null)?0:m.get(A[i])+1);
sum += A[i];
}
for (int i = 0; i < n; ++i) {
int k = sum - A[i];
if (k % 2 == 0) {
k = k >> 1;
// check if array is good after
// removing i-th index element
if (m.containsKey(k)) {
if ((A[i] == k && m.get(k) > 1) || (A[i] != k))
// print good indices
System.out.print( (i + 1) +" ");
}
}
}
}
// Driver Code
public static void main(String args[])
{
int A[] = { 8, 3, 5, 2 };
int n = A.length;
niceIndices(A, n);
}
}
//contributed by Arnab Kundu
Python3
# Python3 program to find all good # indices in the given array from collections import defaultdict # Function to find all good indices # in the given array def niceIndices(A, n): Sum = 0 # hash to store frequency # of each element m = defaultdict(lambda:0) # Storing frequency of each element # and calculating sum simultaneously for i in range(n): m[A[i]] += 1 Sum += A[i] for i in range(n): k = Sum - A[i] if k % 2 == 0: k = k >> 1 # check if array is good after # removing i-th index element if k in m: if ((A[i] == k and m[k] > 1) or (A[i] != k)): # print good indices print((i + 1), end = " ") # Driver Code if __name__ == "__main__": A = [8, 3, 5, 2] n = len(A) niceIndices(A, n) # This code is contributed by Rituraj Jain
C#
// C# program to find all good indices
// in the given array
using System;
using System.Collections.Generic;
class GFG
{
// Function to find all good indices
// in the given array
static void niceIndices(int []A, int n)
{
int sum = 0;
// hash to store frequency
// of each element
Dictionary<int,int> mp = new Dictionary<int,int>();
// Storing frequency of each element
// and calculating sum simultaneously
for (int i = 0 ; i < n; i++)
{
if(mp.ContainsKey(A[i]))
{
var val = mp[A[i]];
mp.Remove(A[i]);
mp.Add(A[i], val + 1);
sum += A[i];
}
else
{
mp.Add(A[i], 0);
sum += A[i];
}
}
for (int i = 0; i < n; ++i)
{
int k = sum - A[i];
if (k % 2 == 0)
{
k = k >> 1;
// check if array is good after
// removing i-th index element
if (mp.ContainsKey(k))
{
if ((A[i] == k && mp[k] > 1) || (A[i] != k))
// print good indices
Console.Write( (i + 1) +" ");
}
}
}
}
// Driver Code
public static void Main(String []args)
{
int []A = { 8, 3, 5, 2 };
int n = A.Length;
niceIndices(A, n);
}
}
/* This code is contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript program to find all good indices
// in the given array
// Function to find all good indices
// in the given array
function niceIndices(A, n)
{
var sum = 0;
// hash to store frequency
// of each element
var m = new Map();
// Storing frequency of each element
// and calculating sum simultaneously
for (var i = 0; i < n; ++i) {
if(m.has(A[i]))
m.set(A[i], m.get(A[i])+1)
else
m.set(A[i], 1)
sum += A[i];
}
for (var i = 0; i < n; ++i) {
var k = sum - A[i];
if (k % 2 == 0) {
k = k >> 1;
// check if array is good after
// removing i-th index element
if (m.has(k)) {
if ((A[i] == k && m.get(k) > 1) || (A[i] != k))
// print good indices
document.write(i + 1 + " ");
}
}
}
}
// Driver Code
var A = [8, 3, 5, 2];
var n = A.length;
niceIndices(A, n);
// This code is contributed by importantly.
</script>
Producción:
1 4
Complejidad de tiempo: O(N*log(N))
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA