Tuesday, May 10, 2011

WAP to find minimum difference between elements of N sorted list of K size each Efficiently..I have done it O(n)

Given an N arrays of size K each.. each of these K elements in the N arrays are sorted, each of these N*K elements are unique. Choose a single element from each of the N arrays, from the chosen subset of N elements. Subtract the minimum and maximum element. Now, this
difference should be least possible Minimum.. Hope the problem is clear :) :)

Sample:

N=3, K=3

N=1 : 6, 16, 67
N=2 : 11,17,68
N=3 : 10, 15, 100

here if 16, 17, 15 are chosen.. we get the minimum difference as
17-15=2.


its very simple question but i saw lot people stuck to solve & approach in this.. i solved it

#include
#include
#include

int min_num(int a,int b ,int c)
{
int m=a;
if(m>b)
m=b;
if(m>c)
m=c;
return m;

}

int max_num(int a,int b,int c)
{
int m=a;
if(m m=b;
if(m m=c;
return m;
}

int minDist(int a[],int b[],int c[], int n)
{

int i = 0,
j = 0, k=0,
min=INT_MAX,
max=INT_MIN,
mins=INT_MAX,
cur;

while(i < n && j < n && k {
max=max_num(a[i],b[j],c[k]);
min=min_num(a[i],b[j],c[k]);

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



cur = abs(max-min);

mins = mins < cur ? mins : cur;


}

return mins;
}

int main()
{

int a[]={6, 16, 67};
int b[]={11,17,68};
int c[]={ 10, 15, 100};
printf("%d\n", minDist(a,b,c,sizeof(a)/sizeof(int)));//all have equal size

return 0;
}


TC O(n)
Run here https://ideone.com/qq4ZN

No comments :