Question
Design an algorithm to find all pairs of integers within an array which sum to a specified value.
Solution
-- If the sum of two is equal to the specified value, print it out
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find all pair of number in array which sum to a specified value
Created Date :
Last Modified : 2-July-2013
============================================================================
*/
#include <iostream>
#include <vector>
#include <iterator>
#include <stdlib.h>
#include <algorithm>
#include <time.h>
#include <list>
using namespace std;
int print_pair(vector<int> &v, int sum)
{
int cnt = 0;
if (v.size() == 1){
cout << "only one element in array" << endl;
}
sort(v.begin(), v.end());
int i = 0;
while(i < v.size()){
if(v.at(i) > sum - v.at(i)
&& std::find(v.begin(), v.end(), sum - v.at(i)) != v.end()){
cout << v.at(i) << " + " << sum - v.at(i) << " = " << sum << endl;
cnt ++;
}
i ++;
while(i < v.size() && v.at(i) == v.at(i - 1)) i ++;
}
if(count_if(v.begin(), v.end(),
[=](int i) -> bool{ return (i == sum / 2) && (sum % 2 == 0);}) > 1){
cout << sum / 2 << " + " << sum / 2 << " = " << sum << endl;
cnt ++;
}
return cnt;
}
int main(int argc, char* argv[])
{
vector<int> v;
int maximum = 20;
//srand((unsigned)time(NULL));
for(int i = 0; i < maximum; i++){
int n = rand() % 35;
v.push_back(n);
}
cout << "original data" << endl;
copy(v.begin(), v.end(), ostream_iterator<int>(cout," "));
cout << endl;
int test_cases[] = {-1, 2, 4, 5, 10, 20, 30, 32, 40, 50, 60};
for(int i = 0; i < sizeof(test_cases)/sizeof(int); ++i){
cout << "Find sum = " << test_cases[i] << endl;
int cnt = print_pair(v, test_cases[i]);
cout << "There are " << cnt << " pairs" << endl << endl;
}
return 0;
}
Output
original data
6 22 34 5 24 9 33 28 12 34 0 5 6 27 21 1 20 7 32 11
Find sum = -1
There are 0 pairs
Find sum = 2
There are 0 pairs
Find sum = 4
There are 0 pairs
Find sum = 5
5 + 0 = 5
There are 1 pairs
Find sum = 10
9 + 1 = 10
5 + 5 = 10
There are 2 pairs
Find sum = 20
11 + 9 = 20
20 + 0 = 20
There are 2 pairs
Find sum = 30
21 + 9 = 30
24 + 6 = 30
There are 2 pairs
Find sum = 32
20 + 12 = 32
21 + 11 = 32
27 + 5 = 32
32 + 0 = 32
There are 4 pairs
Find sum = 40
28 + 12 = 40
33 + 7 = 40
34 + 6 = 40
There are 3 pairs
Find sum = 50
28 + 22 = 50
There are 1 pairs
Find sum = 60
32 + 28 = 60
33 + 27 = 60
There are 2 pairs
Press any key to continue . . .