Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find min diff = |a-b| + |b-c| + |c-a|
Created Data : 12-08-2013
Last Modified : 13-08-2013
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <limits>
#include <iterator>
using namespace std;
long long FindMin3AbsSum(int* arr1, int len1, int* arr2, int len2, int* arr3, int len3)
{
int i(0);
int j(0);
int k(0);
long long minSum = numeric_limits<long long>::max();
auto min3 = [](int a, int b, int c){ return min(a, min(b, c));};
auto max3 = [](int a, int b, int c){ return max(a, max(b, c));};
while(i < len1 && j < len2 && k < len3){
long long sum = 2 * (max3(arr1[i], arr2[j], arr3[k])
- min3(arr1[i], arr2[j], arr3[k]));
if(sum < minSum) minSum = sum;
if(minSum == 0) return 0;
int m3 = min3(arr1[i], arr2[j], arr3[k]);
if(m3 == arr1[i]) i ++;
if(m3 == arr2[j]) j ++;
if(m3 == arr3[k]) k ++;
}
return minSum;
}
void DoTest(int* arr1, int len1, int* arr2, int len2, int* arr3, int len3)
{
cout << "array 1" << endl;
copy(arr1, arr1 + len1, ostream_iterator<int>(cout, " "));
cout << "\narray 2" << endl;
copy(arr2, arr2 + len2, ostream_iterator<int>(cout, " "));
cout << "\narray 3" << endl;
copy(arr3, arr3 + len3, ostream_iterator<int>(cout, " "));
cout << "\nThe min sum of abs difference is " <<
FindMin3AbsSum(
arr1, len1, arr2, len2, arr3, len3) << endl;
cout << "-------------------------" << endl;
}
int main(int argc, char* argv[])
{
int arr1[]={1, 2, 13, 15, 18};
int arr2[]={3, 5, 10, 12, 13};
int arr3[]={2, 4, 6, 12, 13};
DoTest(
arr1, sizeof(arr1) / sizeof(int),
arr2, sizeof(arr2) / sizeof(int),
arr3, sizeof(arr3) / sizeof(int));
int arr4[]={1};
int arr5[]={7, 10, 12, 13};
int arr6[]={2, 4, 6, 12, 13};
DoTest(
arr4, sizeof(arr4) / sizeof(int),
arr5, sizeof(arr5) / sizeof(int),
arr6, sizeof(arr6) / sizeof(int));
return 0;
}
Output
array 1
1 2 13 15 18
array 2
3 5 10 12 13
array 3
2 4 6 12 13
The min sum of abs difference is 0
-------------------------
array 1
1
array 2
7 10 12 13
array 3
2 4 6 12 13
The min sum of abs difference is 12
-------------------------
Press any key to continue . . .
complexitiy: worst case O(n)
diff = |a-b| + |b-c|+|c-a|
where a, b, c are the elements from each array.
Problem
Given 3 Arrays of integer sorted in ascending order, get the sum of minimum difference using one element from each array.
Without loss of generality
assume a > b > c
|a-b| + |b-c| + |c-a|
= (a - b) + (b -c) + (a - c)
= a - c + a - c
= 2(a - c)
let max3 = max(a, b, c)
min3 = min(a, b, c)
= 2(max3 - min3)