Problem
Given 2 equal-length arrays of integers, find pairs, one from each array, that sum to 0.
-- note that one wrinkle of this problem over the more usual form, which is to do this in a single array,
is that you can't use the indexes / iterators crossing each other to know to stop,
rather their /values/ have to cross (if you're doing it right, at or near 0).
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find pairs equal zero
Created Data : 17-06-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <hash_set>
using namespace std;
void FindPairsEqualZero(int *arr1, int* arr2, int len)
{
hash_set<int> h1, h2;
for(int i = 0; i < len; ++i){
h1.insert(arr1[i]);
h2.insert(arr2[i]);
}
for(hash_set<int>::iterator it = h1.begin(); it != h1.end(); ++ it){
if(h2.find(-*it) != h2.end()){
cout << "(" << setw(4) << *it << ", ";
cout << setw(4) << -*it << ")" << endl;
}
}
}
int main(int argc, char* argv[])
{
int *arr1, *arr2;
for(int i = 1; i < 21; ++i){
arr1 = new int[i];
arr2 = new int[i];
for(int j = 0; j < i; ++j){
arr1[j] = rand() % i - i / 2;
arr2[j] = rand() % i - i / 2;
}
cout << "Array 1:" << endl;
for(int j = 0; j < i; ++j){
cout << setw(4) << arr1[j];
}
cout << endl;
cout << "Array 2:" << endl;
for(int j = 0; j < i; ++j){
cout << setw(4) << arr2[j];
}
cout << endl;
FindPairsEqualZero(arr1, arr2, i);
cout << "-------------------------------------------";
}
return 0;
}
Output
Array 1:
0
Array 2:
0
( 0, 0)
-------------------------------------------
Array 1:
-1 0
Array 2:
-1 -1
-------------------------------------------
Array 1:
-1 0 1
Array 2:
-1 1 1
( -1, 1)
( 1, -1)
-------------------------------------------
Array 1:
-1 -1 1 1
Array 2:
1 1 0 -2
( -1, 1)
-------------------------------------------
Array 1:
-1 0 0 -1 1
Array 2:
2 1 0 -1 -2
( -1, 1)
( 0, 0)
( 1, -1)
-------------------------------------------
Array 1:
2 2 0 2 -2 2
Array 2:
-3 -3 1 -2 -3 0
( 2, -2)
( 0, 0)
-------------------------------------------
Array 1:
1 2 -3 -2 1 -3 0
Array 2:
-1 -1 1 -2 -2 1 -3
( 1, -1)
( 2, -2)
-------------------------------------------
Array 1:
-1 -3 0 2 -4 -4 -4 2
Array 2:
1 -2 -1 -2 -2 2 -4 1
( -1, 1)
( 2, -2)
-------------------------------------------
Array 1:
1 3 -1 -1 -4 -4 -4 3 4
Array 2:
2 1 2 -2 1 -3 1 1 -3
( 3, -3)
( -1, 1)
-------------------------------------------
Array 1:
-1 1 2 3 4 -2 4 -1 2 -2
Array 2:
4 -2 3 -3 -4 0 3 -5 1 1
( -1, 1)
( 2, -2)
( 3, -3)
( 4, -4)
-------------------------------------------
Array 1:
0 2 -5 -2 -1 1 4 -2 0 0 -1
Array 2:
-3 4 5 3 -4 -3 -3 1 4 2 1
( -5, 5)
( -2, 2)
( -1, 1)
( 4, -4)
-------------------------------------------
Array 1:
3 4 -3 1 -5 3 -1 -5 -1 -4 -4 3
Array 2:
-2 4 5 3 5 -3 -1 -4 -6 4 4 2
( -5, 5)
( 3, -3)
( -4, 4)
( 4, -4)
( -3, 3)
( 1, -1)
-------------------------------------------
Array 1:
-3 -3 -3 6 1 3 -5 2 -5 1 3 6 -6
Array 2:
-6 -2 -4 4 3 5 -5 -6 3 4 1 -1 -4
( -3, 3)
( 6, -6)
( 1, -1)
( -5, 5)
( 2, -2)
-------------------------------------------
Array 1:
4 -7 5 4 -3 1 6 -5 0 -6 0 -1 6 -1
Array 2:
4 1 1 -2 4 6 6 2 1 -7 0 6 -7 0
( 0, 0)
( -6, 6)
( -1, 1)
-------------------------------------------
Array 1:
7 2 -3 -7 -4 6 -3 1 -4 -7 1 7 -3 5 6
Array 2:
6 7 -5 3 -4 5 1 -7 -4 4 4 1 0 5 0
( 7, -7)
( -3, 3)
( 5, -5)
( -7, 7)
( -4, 4)
-------------------------------------------
Array 1:
-2 6 -2 -1 -4 2 -8 0 2 3 5 -4 1 -6 -3 -3
Array 2:
-5 1 7 0 -1 2 -1 -2 -2 -7 6 0 6 3 -5 4
( -2, 2)
( -1, 1)
( -4, 4)
( 2, -2)
( 0, 0)
( 5, -5)
( 1, -1)
( -6, 6)
( -3, 3)
-------------------------------------------
Array 1:
4 1 8 0 3 -3 -2 -4 0 -1 -2 -2 -4 -8 -7 -3 -3
Array 2:
3 -6 3 1 -8 6 -7 3 -8 2 0 1 4 -6 7 5 7
( -4, 4)
( 0, 0)
( 8, -8)
( -3, 3)
( -2, 2)
( -1, 1)
( -7, 7)
-------------------------------------------
Array 1:
5 -2 4 1 2 -2 -8 4 3 4 -6 -1 -1 8 -3 5 -1 2
Array 2:
-2 -1 -3 0 -6 -5 -8 4 -2 2 -5 4 1 3 -8 -2 -4 -8
( 5, -5)
( -2, 2)
( 4, -4)
( 1, -1)
( 2, -2)
( 3, -3)
( -1, 1)
( 8, -8)
( -3, 3)
-------------------------------------------
Array 1:
-3 -9 -1 -9 2 1 -3 7 -5 -3 -8 8 6 -8 1 5 -9 0 -7
Array 2:
-1 7 -2 7 -2 5 -7 -3 5 -3 7 9 1 8 -6 6 1 7 6
( -9, 9)
( -1, 1)
( 7, -7)
( 2, -2)
( 1, -1)
( -5, 5)
( -8, 8)
( 6, -6)
( -7, 7)
-------------------------------------------
Array 1:
-3 8 -8 7 4 4 2 3 -3 8 3 -7 2 -8 3 -8 -3 -7 -7 -9
Array 2:
-5 1 -5 4 -6 4 9 0 7 7 0 -2 -5 -10 -3 9 -5 -6 2 -9
( -9, 9)
( 2, -2)
( 3, -3)
( -7, 7)
-------------------------------------------
Press any key to continue . . .