Post date: Jun 28, 2013 7:26:53 AM
Problem
Given two unordered list find the greatest common integer.
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Given two unordered list find the greatest common integer
Created Date : 29-Jun-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>
#include <hash_set>
using namespace std;
bool FindGreatestCommonInt(int* arr1, int len1, int* arr2, int len2, int& num )
{
hash_set<int> s1(arr1, arr1 + len1);
hash_set<int> s2(arr2, arr2 + len2);
bool found(false);
for(auto it = s2.begin(); it != s2.end(); ++it){
if(s1.find(*it) != s1.end()){
if(!found){
num = *it;
found = true;
}
if(*it > num) num = *it;
}
}
return found;
}
int main(int argc, char* argv[])
{
int arr1[22] = {1, 3, 5, 7, 9};
int arr2[22] = {4, 8, 12, 16, 20, 22};
int len1(5), len2(6);
cout << "The array1 is " << endl;
copy(arr1, arr1 + len1, ostream_iterator<int>(cout, " "));
cout << endl;
cout << "The array2 is " << endl;
copy(arr2, arr2 + len2, ostream_iterator<int>(cout, " "));
cout << endl;
int maxNum;
if(FindGreatestCommonInt(arr1, len1, arr2, len2, maxNum )) {
cout << "The greatest common integer is " << maxNum << endl;
}
else{
cout << " No common integer in two arrays." << endl;
}
cout << "-----------------------" << endl;
for(int i = 0; i < 10; ++i){
for(int j = 0; j < 21; ++j){
arr1[j] = rand() % 15;
}
for(int j = 0; j < 21; ++j){
arr2[j] = rand() % 15;
}
len1 = rand() % 10 + 1;
len2 = rand() % 10 + 1;
cout << "The array1 is " << endl;
copy(arr1, arr1 + len1, ostream_iterator<int>(cout, " "));
cout << endl;
cout << "The array2 is " << endl;
copy(arr2, arr2 + len2, ostream_iterator<int>(cout, " "));
cout << endl;
if(FindGreatestCommonInt(arr1, len1, arr2, len2, maxNum )) {
cout << "The greatest common integer is " << maxNum << endl;
}
else{
cout << " No common integer in two arrays." << endl;
}
cout << "------------------------" << endl;
}
return 0;
}
Output
The array1 is
1 3 5 7 9
The array2 is
4 8 12 16 20 22
No common integer in two arrays.
-----------------------
The array1 is
11 2 4
The array2 is
9 2 3 7
The greatest common integer is 2
------------------------
The array1 is
3 14 6 1 8 13 2
The array2 is
1 10 2 4 13 11 0
The greatest common integer is 13
------------------------
The array1 is
11
The array2 is
6
No common integer in two arrays.
------------------------
The array1 is
6 4 1 10 12 11 7
The array2 is
10 3
The greatest common integer is 10
------------------------
The array1 is
3 9 3 4
The array2 is
2 13 4 14
The greatest common integer is 4
------------------------
The array1 is
13 12 4 8 8
The array2 is
14 10 2 8 11 0 13
The greatest common integer is 13
------------------------
The array1 is
11 3 2 6 1
The array2 is
13 7 10 2 10 13 1 12 12 7
The greatest common integer is 2
------------------------
The array1 is
1 2
The array2 is
10 8 7 5 9 9 1 11 1
The greatest common integer is 1
------------------------
The array1 is
6 7 1 4
The array2 is
9
No common integer in two arrays.
------------------------
The array1 is
2 7 3 2 13 5
The array2 is
2 11 6 13
The greatest common integer is 13
------------------------
Press any key to continue . . .