## Find The Minimum Difference

### October 15, 2013

This is rather straight forward, though I admit it took a few tries to get all the less thans and minus signs in the right place:

`(define (f xs ys)`

(let ((d (- (car xs) (car ys))))

(let loop ((xs xs) (ys ys) (diff (abs d)))

(cond ((or (null? xs) (null? ys)) diff)

((< (car xs) (car ys))

(let ((d (- (car ys) (car xs))))

(loop (cdr xs) ys (min d diff))))

(else (let ((d (- (car xs) (car ys))))

(loop xs (cdr ys) (min d diff))))))))

For example:

`> (f '(19 22 24) '(37 38 49 88))`

13

The difference of 13 appears between 24 of the first array and 37 of the second array.

Assuming that the longer of the two arrays has length *n*, the algorithm given above has time complexity O(*n*). If the arrays weren’t sorted, you could sort them and then scan, giving a O(*n* log *n*) algorithm, or you could compare the items one-by-one for an O(*n*^{2}) algorithm.

You can run the program at http://programmingpraxis.codepad.org/4bWj9XMf.

Pages: 1 2

In Python:

While this won’t change the average complexity, can’t we shortcircuit if we find an absolute difference of zero?

We can shortcuit if we find a difference of one. Zero is not possible, as the arrays do not have common numbers.

Thanks @Paul, I didn’t read carefully enough!

I hate to be a pain, but it’s not clear to me that the arrays have to be nonempty.

Here’s a Haskell version that handles empty lists as well:

This could have been cleaner if infinity were included in the integers in Haskell;

it’s true that

`1/0`

returns`Infinity`

, but this isn’t an`Integer`

.Sorry for spamming, but here’s a slightly cleaner version of my

`mad`

function:Python version. Like Paul’s, but i put the iterators in a separate generator that returns potential minimum pairs from the lists. Then maxdiff() is straight forward.

def pairs(xs, ys):

itx, ity = iter(xs), iter(ys)

x, y = next(itx), next(ity)

while True:

yield x, y

x, y = (next(itx),y) if x < y else (x, next(ity))

def mindiff(xs, ys):

return min(abs(x – y) for x,y in pairs(xs, ys))

Sorry, forgot the formating.

Python version. Like Paul’s, but i put the iterators in a separate generator that returns potential minimum pairs from the lists. Then maxdiff() is straight forward.

Here is my solution in groovy. I have a feeling there is a more efficient way to do this especially with the the def min at the start.

static int minDiff(arr1, arr2){

def min = Math.abs(arr1[0]-arr2[0])

for(i in arr1){

for(j in arr2){

def diff = Math.abs(i-j)

if(min>diff){

min=diff

}

}

}

return min

}

Most of this stuff is well over my head, but I happen to be just starting to learn APL and so could’t resist. Using the example input from the first solution:

f←{⌊/⌊/|⍺∘.-⍵}

x←19 22 24

y←37 38 49 88

x f y

13

I don’t kow if there’s a clever mathy way to make it more efficient, but at least it has the virtue of simplicity. I guess this will run in O(n^2)… :-)

As for empty vectors, I am not sure what the subtraction operator should yield without any arguments, but I get infinity when I feed it to my function:

⍬ f ⍬

∞

Here’s my version in C#. As a small optimization for large arrays, I’ve added a short-circuit that exits if the difference between x and y-currrent is positive and greater than the abs difference between x and y-previous (since the arrays are guaranteed to be sorted, this means we won’t find a smaller difference for x).

Here is my version in C++:

#include

#include

#include

#include

#include

using namespace std;

#define N 10

struct small {

int diff;

int x;

int i;

int y;

int j;

} ;

int get_num();

int ascending(int *, int);

int main(){

int j,i=0;

int n=N;

int x[N];

int y[N];

int status;

struct small sm;

sm.x=sm.y=sm.i=sm.j=0;

sm.diff=1000;

while(i<n){

x[i++] = get_num();

}

cout<<"X:"<<endl;

for(i=0;i<n;i++)

cout<<' '<<x[i];

cout<<' '<<endl;

i=0;

while(i<n){

int num = get_num();

status = false;

for(j=0;j<n&&num==x[j];j++)

status =true;

if(status == false)

y[i++]

=num;

}

cout<<"Y:"<<endl;

for(i=0;i<n;i++)

cout<<' '<<y[i];

cout<<endl;

cout<<"After ascending:"<<endl;

ascending(x,n);

cout<<"X:"<<endl;

for(i=0;i<n;i++)

cout<<' '<<x[i];

cout<<endl;

ascending(y,n);

cout<<"Y:"<<endl;

for(i=0;i<n;i++)

cout<<' '<<y[i];

cout<<endl;

for(i=0;i<n;i++)

for(j=0;j<n;j++) {

if(abs(x[i]-y[j]) <sm.diff)

{

sm.diff=abs(x[i]-y[j]);

sm.i=i;

sm.j=j;

sm.x=x[i];

sm.y=y[j];

}

}

cout<<"diff:"<<sm.diff<<endl;

cout<<"nums:"<<sm.x<<' '<<sm.y<<endl;

return 0;

}

int get_num(){

num:

int n = rand()%100;

if(n!=0)

return n;

else

goto num;

}

int ascending(int *num, int n){

int temp=0;

int j,i=0;

for(i=0;i<n;i++)

for(j=0;jnum[j+1]){

temp=num[j];

num[j]=num[j+1];

num[j+1]=temp;

}

}

return true;

}

A shorter haskell solution

import Control.Monad

minDiff (x:xs) (y:ys) | x – y < 0 = choose (y-x) $ minDiff xs (y:ys)

| otherwise = choose (x-y) $ minDiff (x:xs) ys

where choose x m = fmap (min x) m `mplus` Just x

minDiff _ _ = Nothing