#### Variant of the 2-sum algorithm with a range of sums

By JoyjitC

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.

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]. #### @olegarch 2016-09-01 02:04:21

Source 2sum.c:

``````#include <stdio.h>
#include <strings.h>

#define MAXVAL 10000

int main(int argc, char **argv) {
// init vars
int i, t, rc = 0;
unsigned arr[2 * MAXVAL + 1], *p0 = arr + MAXVAL;
bzero(arr, sizeof(arr));

FILE *f = fopen(argv, "r");
if(f == NULL)
return -1; // unable to open file

char buf;
while(fgets(buf, sizeof(buf), f))
p0[atoi(buf)]++;

t = atoi(argv); // Target sum

for(i = -MAXVAL; i <= MAXVAL; i++)
rc += p0[i] * p0[t - i];

printf("Combinations: %d\n", rc >> 1);
return fclose(f);
}
``````

Test file 2sum.txt:

``````5
5
10
10
1
-5
``````

Run examples:

``````\$ ./a.out 2sum.txt 0
Combinations: 2

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

\$ ./a.out 2sum.txt 13
Combinations: 0
``````

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); // 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.

### [SOLVED] How to sum array of numbers in Ruby?

• 2009-10-08 16:04:57
• brainfck
• 449578 View
• 569 Score
• Tags:   ruby arrays math sum