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;


}

dada

• 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;


            }


        }


        


    }


    


    


    return totalCounts;


}


 


/**


 * 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;


    


}