Problem
Given a sorted array. Find the number of couples with the same difference.
For example we can have an array with 2 couples whose difference is 3 and 4 couples whose difference is 5.
The Output should be 2 & 4.
Solution
Select any 2 elements, compute their difference
Use hash_map to store the difference and count
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find the number of couples with the same difference
Created Date : 13-July-2013
Last Modified :
===========================================================================
*/
#include <iostream>
#include <iomanip>
#include <hash_map>
#include <cassert>
using namespace std;
void PrintPairCount(int* arr, int len)
{
hash_map<int, int> hm;
for(int i = 1; i < len; ++i){
for(int j = 0; j < i; ++j){
int d = arr[i] - arr[j];
auto it = hm.find(d);
if(it == hm.end()){
hm.insert(pair<int, int>(d, 1));
}
else{
it->second ++;
}
}
}
cout << "The output is " << endl;
int count(0);
for(auto it = hm.begin(); it != hm.end(); ++it){
if(it->second != 1){
cout << "Find " << it->second << " pairs with difference of ";
cout << it->first << endl;
count ++;
}
}
if(count == 0){
cout << "No pair shares the same difference" << endl;
}
}
void DoTest(int* arr, int len)
{
assert(arr != NULL);
assert(len > 0);
cout << "The array is " << endl;
for(int i = 0; i < len; ++i){
cout << setw(4) << arr[i];
}
cout << endl;
PrintPairCount(arr, len);
cout << "----------------------------------"<< endl;
}
int main(int argc, char* argv[])
{
int arr[] = {1};
DoTest(arr, sizeof(arr) / sizeof(arr[0]));
int arr1[] = {1, 3};
DoTest(arr1, sizeof(arr1) / sizeof(arr1[0]));
int arr2[] = {1, 1};
DoTest(arr2, sizeof(arr2) / sizeof(arr2[0]));
int arr3[] = {1, 3, 5};
DoTest(arr3, sizeof(arr3) / sizeof(arr3[0]));
int arr4[] = {1, 2, 3, 5, 7, 7 , 8, 9};
DoTest(arr4, sizeof(arr4) / sizeof(arr4[0]));
int arr5[] = {-1, 1, 1, 1, 3, 4, 5, 7, 9};
DoTest(arr5, sizeof(arr5) / sizeof(arr5[0]));
return 0;
}
Output
The array is
1
The output is
No pair shares the same difference
----------------------------------
The array is
1 3
The output is
No pair shares the same difference
----------------------------------
The array is
1 1
The output is
No pair shares the same difference
----------------------------------
The array is
1 3 5
The output is
Find 2 pairs with difference of 2
----------------------------------
The array is
1 2 3 5 7 7 8 9
The output is
Find 5 pairs with difference of 1
Find 6 pairs with difference of 2
Find 4 pairs with difference of 4
Find 2 pairs with difference of 3
Find 4 pairs with difference of 6
Find 3 pairs with difference of 5
Find 2 pairs with difference of 7
----------------------------------
The array is
-1 1 1 1 3 4 5 7 9
The output is
Find 9 pairs with difference of 2
Find 3 pairs with difference of 0
Find 4 pairs with difference of 8
Find 6 pairs with difference of 4
Find 2 pairs with difference of 5
Find 4 pairs with difference of 3
Find 2 pairs with difference of 1
Find 5 pairs with difference of 6
----------------------------------
Press any key to continue . . .