Dada una array de N elementos, la tarea es verificar si la array tiene un elemento que es igual a la suma de todos los elementos restantes.
Ejemplos :
Input: a[] = {5, 1, 2, 2}
Output: Yes
we can write 5=(1+2+2)
Input: a[] = {2, 1, 2, 4, 3}
Output: No
Enfoque: suponga que el total de elementos en la array es N . Ahora, si existe algún elemento tal que el elemento sea igual a la suma de los elementos restantes, entonces se puede decir que la array se puede dividir en dos mitades con la misma suma, de modo que una mitad tiene solo un elemento con valor sum/2 .
Además, dado que ambas mitades tienen la misma suma, la suma total de la array debe ser par, ya que sabemos que:
- IMPAR + IMPAR = PAR
- PAR + PAR = PAR
Algoritmo :
- Iterar sobre la array y contar la aparición de todos los elementos y almacenarlos en un mapa . También sume los elementos de la array.
- La condición dada en el problema solo es posible cuando se cumplen las siguientes condiciones.
- La suma total de la array es par
- La ocurrencia sum/2 en la array debe ser igual a al menos 1.
- Si no se cumplen las condiciones anteriores, no es posible eliminar ningún elemento de este tipo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to Check if the array
// has an element which is equal to sum
// of all the remaining elements
#include <bits/stdc++.h>
using namespace std;
// Function to check if such element exists or not
bool isExists(int a[], int n)
{
// Storing frequency in map
unordered_map<int, int> freq;
// Stores the sum
int sum = 0;
// Traverse the array and count the
// array elements
for (int i = 0; i < n; i++) {
freq[a[i]]++;
sum += a[i];
}
// Only possible if sum is even
if (sum % 2 == 0) {
// If half sum is available
if (freq[sum / 2])
return true;
}
return false;
}
// Driver code
int main()
{
int a[] = { 5, 1, 2, 2 };
int n = sizeof(a) / sizeof(a[0]);
if (isExists(a, n))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java program to Check if the array
// has an element which is equal to sum
// of all the remaining elements
import java.util.*;
class Solution{
// Function to check if such element exists or not
static boolean isExists(int a[], int n)
{
// Storing frequency in map
Map<Integer, Integer> freq= new HashMap<Integer, Integer>();
// Stores the sum
int sum = 0;
// Traverse the array and count the
// array elements
for (int i = 0; i < n; i++) {
freq.put(a[i],freq.get(a[i])==null?0:freq.get(a[i])+1);
sum += a[i];
}
// Only possible if sum is even
if (sum % 2 == 0) {
// If half sum is available
if (freq.get(sum / 2)!=null)
return true;
}
return false;
}
// Driver code
public static void main(String args[])
{
int a[] = { 5, 1, 2, 2 };
int n = a.length;
if (isExists(a, n))
System.out.println( "Yes");
else
System.out.println( "No");
}
}
//contributed by Arnab Kundu
Python3
# Python3 code to check if the array has
# an element which is equal to sum of all
# the remaining elements
# function to check if such element
# exists or not
def isExists(a, n):
# storing frequency in dict
freq = {i : 0 for i in a}
#stores the sum
Sum = 0
# traverse the array and count
# the array element
for i in range(n):
freq[a[i]] += 1
Sum += a[i]
# Only possible if sum is even
if Sum % 2 == 0:
#if half sum is available
if freq[Sum // 2]:
return True
return False
# Driver code
a = [5, 1, 2, 2]
n = len(a)
if isExists(a, n):
print("Yes")
else:
print("No")
# This code is contributed
# by Mohit Kumar
C#
// C# program to Check if the array
// has an element which is equal to sum
// of all the remaining elements
using System;
using System.Collections.Generic;
class Solution
{
// Function to check if such element exists or not
static Boolean isExists(int []arr, int n)
{
// Storing frequency in map
Dictionary<int, int> m = new Dictionary<int, int>();
// Stores the sum
int sum = 0;
// Traverse the array and count the
// array elements
for (int i = 0; i < n; i++)
{
if(m.ContainsKey(arr[i]))
{
var val = m[arr[i]];
m.Remove(arr[i]);
m.Add(arr[i], val + 1);
}
else
{
m.Add(arr[i], 1);
}
sum += arr[i];
}
// Only possible if sum is even
if (sum % 2 == 0)
{
// If half sum is available
if (m[sum / 2] != 0)
return true;
}
return false;
}
// Driver code
public static void Main()
{
int []a = { 5, 1, 2, 2 };
int n = a.Length;
if (isExists(a, n))
Console.WriteLine( "Yes");
else
Console.WriteLine( "No");
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// JavaScript program to Check if the array
// has an element which is equal to sum
// of all the remaining elements
// Function to check if such element exists or not
function isExists(a, n)
{
// Storing frequency in map
let freq= new Map();
// Stores the sum
let sum = 0;
// Traverse the array and count the
// array elements
for (let i = 0; i < n; i++) {
freq.set(a[i],freq.get(a[i])==null?0:freq.get(a[i])+1);
sum += a[i];
}
// Only possible if sum is even
if (sum % 2 == 0) {
// If half sum is available
if (freq.get(sum / 2)!=null)
return true;
}
return false;
}
// Driver Code
let a = [ 5, 1, 2, 2 ];
let n = a.length;
if (isExists(a, n))
document.write( "Yes");
else
document.write( "No");
</script>
Producción:
Yes
Complejidad de tiempo: O(N)
Espacio auxiliar: O(N)
Otro enfoque: Calcular total = suma de todos los elementos de la array. Luego ejecute un bucle FOR para verificar si cada elemento * 2 == total. Si se encuentra alguno de estos elementos, devuelve True, de lo contrario False al final del ciclo. Complejidad de tiempo = O(N), complejidad de espacio = O(1).