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

Showing Answers 1 - 3 of 3 Answers

Jin Hyuk Cho

  • Feb 3rd, 2016
 

Working example

Code
  1. #include <iostream>

  2. #include <vector>

  3. #include <algorithm>

  4.  

  5.  

  6. int findTwoSumZero (vector<int> &original) {

  7.     // clone array

  8.     vector<int> numbers(original);

  9.    

  10.     // sort numbers

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

  12.    

  13.     // front and back

  14.     size_t front = 0;

  15.     size_t back = numbers.size() -1;

  16.    

  17.     // result

  18.     int count = 0;

  19.     int frontMul = 1;

  20.     int backMul = 1;

  21.     while (front < back) {

  22.         int frontValue = numbers[front];

  23.         int backValue = numbers[back];

  24.        

  25.         // non-unique number support

  26.         if (frontValue == numbers[front+1]) {

  27.             ++front;

  28.             ++frontMul;

  29.             continue;

  30.         }

  31.         if (backValue == numbers[back-1]) {

  32.             --back;

  33.             ++backMul;

  34.             continue;

  35.         }

  36.        

  37.         int sum = frontValue + backValue;

  38.         if (sum == 0) {

  39.             count += frontMul * backMul;

  40.             ++front;

  41.             --back;

  42.             frontMul = 1;

  43.             backMul = 1;

  44.         } else if (sum > 0) {

  45.             --back;

  46.             backMul = 1;

  47.         } else if (sum < 0) {

  48.             ++front;

  49.             frontMul = 1;

  50.         }

  51.        

  52.     }

  53.    

  54.     return count;

  55. }

  56.  

  57. int main () {

  58.    

  59.     vector<int> numbers;

  60.     numbers.push_back(-3);

  61.     numbers.push_back(-5);

  62.     numbers.push_back(-3);

  63.     numbers.push_back(3);

  64.     cout << findTwoSumZero(numbers) << endl;

  65.    

  66.     return 0;

  67. }

  Was this answer useful?  Yes

dada

  • Feb 6th, 2016
 

This solution is O(n)

Code
  1. #include <iostream>

  2. #include <vector>

  3. #include <limits>

  4. #include <algorithm>

  5. #include <random>

  6.  

  7. using namespace std;

  8.  

  9. #define MAX_NUM 10000

  10.  

  11. int main()

  12. {

  13.         vector<int> in(MAX_NUM); //input data

  14.  

  15.         // fill input data with some random numbers

  16.         std::mt19937 gen(0);

  17.         std::uniform_int_distribution<int> dis(-MAX_NUM+1, MAX_NUM-1);

  18.  

  19.         for (int i = 0; i < MAX_NUM; ++i)

  20.         {

  21.                 in[i] = dis(gen);

  22.         }

  23.        

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

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

  26.  

  27.         // go through input data and populate poscount and negcount

  28.         for (auto it = in.begin(); it != in.end(); ++it)

  29.         {

  30.                 int val = *it;

  31.                

  32.                 if (val < 0)

  33.                 {

  34.                         ++negcount[-val];

  35.                 }

  36.                 else

  37.                 {

  38.                         ++poscount[val];

  39.                 }

  40.         }

  41.  

  42.         unsigned long numSumZeroes=0;

  43.         // number of pairs formed of negative and positive numbers of same value will be minimum of pos and neg values

  44.         for (int i = 0; i < poscount.size() - 1; ++i)

  45.         {

  46.                 numSumZeroes += min(negcount[i], poscount[i]);

  47.         }

  48.         cout << "Number of pairs of numbers whose sum is 0 is: " << numSumZeroes << endl;

  49.         return 0;

  50. }

  51.  

  Was this answer useful?  Yes

Jin Hyuk Cho

  • Feb 8th, 2016
 

O(n) solution

Code
  1. #include <iostream>

  2. #include <string>

  3. #include <vector>

  4. #include <queue>

  5. #include <set>

  6. #include <locale>         // std::locale, std::isdigit

  7. #include <sstream>

  8. #include <algorithm>

  9. #include <iterator>

  10. #include <map>

  11.  

  12. int findTwoSumZeroUsingHashMap (vector<int> &original) {

  13.     int totalCounts = 0;

  14.     map<int,int> counts;

  15.     // construct occurance map

  16.     for (int i : original) {

  17.         if (counts.find(i) == counts.end()) {

  18.             counts.insert(std::map<int, int>::value_type(i, 1));

  19.         } else {

  20.             ++counts[i];

  21.         }

  22.     }

  23.    

  24.     // iterate over the occurance map

  25.     for (auto count : counts) {

  26.         // cout << count.first << "=" << count.second << endl;

  27.         int number = count.first;

  28.         int numberCount = count.second;

  29.         int complement = -number;

  30.         if (number > 0) {

  31.             if (counts.find(complement) != counts.end()) {

  32.                 // complement found

  33.                 // complements count * numbers count

  34.                 totalCounts += counts[complement] * numberCount;

  35.             }

  36.         } else if (number == 0) {

  37.             if (numberCount == 2) {

  38.                 ++totalCounts;

  39.             } else if (numberCount > 2){

  40.                 totalCounts += numberCount * (numberCount - 1) / 2;

  41.             }

  42.         }

  43.        

  44.     }

  45.    

  46.    

  47.     return totalCounts;

  48. }

  49.  

  50. /**

  51.  * Main executable

  52.  */

  53. int main () {

  54.    

  55.     vector<int> numbers;

  56.     numbers.push_back(1);

  57.     numbers.push_back(1);

  58.     numbers.push_back(2);

  59.     numbers.push_back(3);

  60.     numbers.push_back(-1);

  61.     numbers.push_back(-1);

  62.     cout << findTwoSumZeroUsingHashMap(numbers) << endl;

  63.    

  64.     return 0;

  65.    

  66. }

  Was this answer useful?  Yes

Give your answer:

If you think the above answer is not correct, Please select a reason and add your answer below.

 

Related Answered Questions

 

Related Open Questions