2016-08-16 09:50:05 8 Comments

**The problem statement is as follows:**

The goal of this problem is to implement a variant of the 2-SUM algorithm.

The file contains 1 million integers, both positive and negative (there might be some repetitions!).This is your array of integers, with the ith row of the file specifying the ith entry of the array.

Your task is to compute the number of target values t in the interval [-10000,10000] (inclusive) such that there are distinct numbers x,y in the input file that satisfy x+y=t.

Write your numeric answer (an integer between 0 and 20001).

**I have implemented a naive solution:**

```
#include <iostream>
#include <fstream>
#include <unordered_set>
#include <vector>
#include <algorithm>
#define FILE "2sum.txt"
#define LEFT -10000
#define RIGHT 10000
using namespace std;
class cal_2sum{
int count;
unordered_set<long> hashT;
vector<long> array;
public:
cal_2sum(){
count = 0;
}
int getCount(){
return this->count;
}
int calculate(string filename,int left, int right){
ifstream file(filename);
long num;
while(file>>num){
hashT.insert(num);
}
for(auto it = hashT.begin(); it != hashT.end(); ++it)
array.push_back(*it);
sort(array.begin(),array.end());
for(long target = left; target<=right; target++){
bool found = false;
for(auto it = array.begin(); it != array.end(); ++it){
long otherHalf = target - (*it);
auto verdict = hashT.find(otherHalf);
if(verdict != hashT.end() && (*verdict) != (*it)){
found = true;
break;
}
}
if(found == true)
count++;
cout<<count<<endl;
}
}
};
int main(){
cal_2sum res;
res.calculate(FILE,LEFT,RIGHT);
cout<<res.getCount()<<endl;
return 0;
}
```

**It gives the correct answer, but, it is too slow. How can i improve the solution.**
The input numbers are in the range [-99999887310
,99999662302].

### Related Questions

#### Sponsored Content

#### 59 Answered Questions

### [SOLVED] Does JavaScript have a method like "range()" to generate a range within the supplied bounds?

**2010-10-09 02:37:29****alex****580230**View**779**Score**59**Answer- Tags: javascript arrays functional-programming

#### 23 Answered Questions

#### 41 Answered Questions

### [SOLVED] How to find the sum of an array of numbers

**2009-08-04 22:29:40****akano1****998086**View**734**Score**41**Answer- Tags: javascript jquery arrays

#### 13 Answered Questions

#### 1 Answered Questions

#### 1 Answered Questions

#### 5 Answered Questions

### [SOLVED] How do you recursively count the number of negative numbers in an array (Java)?

**2013-03-28 18:06:43****rphello101****9489**View**0**Score**5**Answer- Tags: java arrays recursion negative-number

#### 1 Answered Questions

### [SOLVED] Variant Of Two Sum Solution Extremely Slow in Objective C

**2016-08-27 05:02:35****jac300****160**View**0**Score**1**Answer- Tags: python objective-c algorithm hashtable big-o

#### 1 Answered Questions

### [SOLVED] How to remove an element from an array and then shift other elements over?

**2014-09-10 04:48:21****T-Bird****592**View**0**Score**1**Answer- Tags: c++ arrays visual-studio sorting

## 1 comments

## @olegarch 2016-09-01 02:04:21

Source 2sum.c:

Test file 2sum.txt:

Run examples:

For huge range, change array arr to hashtable.

## @c f 2016-10-05 17:39:11

If you are still active, could you help me understand, 1.

`$ ./a.out 2sum.txt 15 = Combinations: 4`

I dont know how this is right because you have (10,5) or (5,10) 2. In your code, t is supposed to be between -10000 and 10000 but you have set its value on the command line`t = atoi(argv[2]); // Target sum`

and then change the value of i to be between -10000 and 10000 Hope I'm not missing something.## @olegarch 2016-10-07 22:25:08

1. I have two of 10 and two of 5 in the my file, since you stated: (there might be some repetitions!), and needed count all possible combinations. So, my 4 combinations are: (10a 5a), (10b 5a), (10a 5b) (10b 5b). If you needed compute some number just once, change the line "p0[atoi(buf)]++;" to "p0[atoi(buf)] = 1;". If you would like limit target - just add if() statement, I think, this is easy.