By JoyjitC


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].

1 comments

@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[1], "r");
  if(f == NULL)
    return -1; // unable to open file

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

  t = atoi(argv[2]); // 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[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.

Related Questions

Sponsored Content

43 Answered Questions

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

15 Answered Questions

[SOLVED] How to sum a variable by group

10 Answered Questions

[SOLVED] How to sort in-place using the merge sort algorithm?

17 Answered Questions

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

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

2 Answered Questions

[SOLVED] How to implement classic sorting algorithms in modern C++?

5 Answered Questions

1 Answered Questions

1 Answered Questions

fstream is failing to overwrite the contents of my text file

Sponsored Content