# Solve this using C++ code

Write a solution in any language to the following: Given a large list of integers (more than 1 000 000 values) find how many ways there are of selecting two of them that add up to 0

#### Jin Hyuk Cho

• Feb 3rd, 2016

Working example

```Code#include <iostream>
#include <vector>
#include <algorithm>

int findTwoSumZero (vector<int> &original) {
// clone array
vector<int> numbers(original);

// sort numbers
sort(numbers.begin(), numbers.end());

// front and back
size_t front = 0;
size_t back = numbers.size() -1;

// result
int count = 0;
int frontMul = 1;
int backMul = 1;
while (front < back) {
int frontValue = numbers[front];
int backValue = numbers[back];

// non-unique number support
if (frontValue == numbers[front+1]) {
++front;
++frontMul;
continue;
}
if (backValue == numbers[back-1]) {
--back;
++backMul;
continue;
}

int sum = frontValue + backValue;
if (sum == 0) {
count += frontMul * backMul;
++front;
--back;
frontMul = 1;
backMul = 1;
} else if (sum > 0) {
--back;
backMul = 1;
} else if (sum < 0) {
++front;
frontMul = 1;
}

}

return count;
}

int main () {

vector<int> numbers;
numbers.push_back(-3);
numbers.push_back(-5);
numbers.push_back(-3);
numbers.push_back(3);
cout << findTwoSumZero(numbers) << endl;

return 0;
}```

• Feb 6th, 2016

This solution is O(n)

```Code#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>
#include <random>

using namespace std;

#define MAX_NUM 10000

int main()
{
vector<int> in(MAX_NUM); //input data

// fill input data with some random numbers
std::mt19937 gen(0);
std::uniform_int_distribution<int> dis(-MAX_NUM+1, MAX_NUM-1);

for (int i = 0; i < MAX_NUM; ++i)
{
in[i] = dis(gen);
}

vector<int> poscount(MAX_NUM, 0); // poscount[i] will have the count of occurances of number i
vector<int> negcount(MAX_NUM, 0); // negcount[i] will have the count of occurances of number -i

// go through input data and populate poscount and negcount
for (auto it = in.begin(); it != in.end(); ++it)
{
int val = *it;

if (val < 0)
{
++negcount[-val];
}
else
{
++poscount[val];
}
}

unsigned long numSumZeroes=0;
// number of pairs formed of negative and positive numbers of same value will be minimum of pos and neg values
for (int i = 0; i < poscount.size() - 1; ++i)
{
numSumZeroes += min(negcount[i], poscount[i]);
}
cout << "Number of pairs of numbers whose sum is 0 is: " << numSumZeroes << endl;
return 0;
}
```

#### Jin Hyuk Cho

• Feb 8th, 2016

O(n) solution

```Code#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <locale>         // std::locale, std::isdigit
#include <sstream>
#include <algorithm>
#include <iterator>
#include <map>

int findTwoSumZeroUsingHashMap (vector<int> &original) {
int totalCounts = 0;
map<int,int> counts;
// construct occurance map
for (int i : original) {
if (counts.find(i) == counts.end()) {
counts.insert(std::map<int, int>::value_type(i, 1));
} else {
++counts[i];
}
}

// iterate over the occurance map
for (auto count : counts) {
// cout << count.first << "=" << count.second << endl;
int number = count.first;
int numberCount = count.second;
int complement = -number;
if (number > 0) {
if (counts.find(complement) != counts.end()) {
// complement found
// complements count * numbers count
totalCounts += counts[complement] * numberCount;
}
} else if (number == 0) {
if (numberCount == 2) {
++totalCounts;
} else if (numberCount > 2){
totalCounts += numberCount * (numberCount - 1) / 2;
}
}

}

}

/**
* Main executable
*/
int main () {

vector<int> numbers;
numbers.push_back(1);
numbers.push_back(1);
numbers.push_back(2);
numbers.push_back(3);
numbers.push_back(-1);
numbers.push_back(-1);
cout << findTwoSumZeroUsingHashMap(numbers) << endl;

return 0;

}```