Given 3 sorted arrays (in ascending order). Let the arrays be A(of n1 length), B(of n2 length), C(of n3 length). Let x be an element of A, y of B, z of C. The distance between x, y and z is defined as the max(|x-y|,|y-z|,|z-x|). Find the tuple with the minimum distance?

#include <stdio.h>
#include <limits.h>

#define min2(a,b) (a) < (b) ? (a) : (b)
#define min3(a,b,c) (a) < (b) ? min2(a,c) : min2(b,c)
#define max2(a,b) (a) > (b) ? (a) : (b)
#define max3(a,b,c) (a) > (b) ? max2(a,c) : max2(b,c)


typedef struct
{
int x, y, z;
}Tuple;


Tuple mindist(int a[], int b[], int c[], int m, int n, int l)
{
int i = 0;
int j = 0;
int k = 0;

int distance = INT_MAX;
Tuple out = {-1,-1,-1};


while(i < m && j < n && k < l)
{
//Find max (abs(a[i]-b[j]), abs(b[j]-c[k]), abs(a[i]-c[k])
//Advance minimum of a[i], b[j] and c[l]

int x = abs(a[i]-b[j]);
int y = abs(b[j]-c[k]);
int z = abs(a[i]-c[k]);

int d = max3(x,y,z);
if(d < distance)
{
distance = d;
out.x = i; out.y = j, out.z = k;
}

int min = min3(a[i], b[j], c[k]);

if(min == a[i])
i++;
else if(min == b[j])
j++;
else if(min == c[k])
k++;

}
return out;

}


int main()
{
int m, n, l;

scanf("%d%d%d", &m,&n,&l);

int a[m];
int b[n];
int c[l];

int i;

for(i = 0; i < m; ++i )
scanf("%d", a + i);


for(i = 0; i < n; ++i )
scanf("%d", b + i);

for(i = 0; i < l; ++i )
scanf("%d", c + i);

Tuple r = mindist(a,b,c,m,n,l);

printf("(%d,%d,%d)\n", r.x,r.y,r.z);
}
83,1 Bot
Advertisements

One thought on “Given 3 sorted arrays (in ascending order). Let the arrays be A(of n1 length), B(of n2 length), C(of n3 length). Let x be an element of A, y of B, z of C. The distance between x, y and z is defined as the max(|x-y|,|y-z|,|z-x|). Find the tuple with the minimum distance?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s