ronith
6/20/2018 - 5:50 PM

Check if there exist two elements in an array whose sum is equal to the sum of rest of the array

We have an array of integers and we have to find two such elements in the array such that sum of these two elements is equal to the sum of rest of elements in array.

Examples:

Input : arr[] = {2, 11, 5, 1, 4, 7} Output : Elements are 4 and 11 Note that 4 + 11 = 2 + 5 + 1 + 7

Input : arr[] = {2, 4, 2, 1, 11, 15} Output : Elements do not exist

An efficient solution is to find sum of all array elements. Let this sum be “sum”. Now the task reduces to finding a pair with sum equals to sum/2. Another optimization is, a pair can exist only if the sum of whole array is even because we are basically dividing it into two parts with equal sum.

1- Find the sum of whole array. Let this sum be “sum” 2- If sum is odd, return false. 3- Find a pair with sum equals to “sum/2” using hashing based method discussed here as method 2. If a pair is found, print it and return true. 4- If no pair exists, return false.

// https://www.geeksforgeeks.org/check-exist-two-elements-array-whose-sum-equal-sum-rest-array/
#include <iostream>
#include <set>
using namespace std;

void func(int a[],int n){
    int sum=0;
    for (int i=0;i<n;i++)
        sum+=a[i];

    if (sum%2==1){
        cout<< "No such pair exists!";
        exit(0);
    }

    sum/=2;
    set <int> s;
    for(int i=0;i<n;i++) {
        int v=sum-a[i];

        if (s.find(v) != s.end()){
            cout<< "Elements are: " << a[i] << " and " << v ;
            exit(0);
        }
        s.insert(a[i]);
    }
    cout<< "No such pair exists!";
}

int main() {
    int n;
    cin>>n;
    int a[n];
    for (int i=0;i<n;i++)
        cin>>a[i];

    func(a,n);
}