I have come up with this approach. Take first two arrays and compute the min
absolute difference between two elements. Then with this mingap2 between A1
and A2, add each element and check what is the least value possible.
Below is the code. Think it should work. I have not considered negative
numbers for my soln.
#include<iostream>
using namespace std;
int FindGap3Arrays(int *a1, int m, int *a2, int n, int *a3, int p)
{
int mingap2 = 9999;
int mingap3 = 9999;
int index1;
int index2;
int index3;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
if(abs(a1[m]-a2[n])<mingap2)
{
mingap2 = abs(a1[m]-a2[n]);
index1 = i;
index2 = j;
}
for(int k=0;k<p;k++)
{
if(mingap2+a3[k]<mingap3)
mingap3 = mingap2+a3[k];
index3 = k;
}
return mingap3;
}
int main()
{
int *A1;
int *A2;
int *A3;
int m,n,p;
cout<<"\nEnter the value of m, n and p :";
cin>>m>>n>>p;
A1 = new int[m];
A2 = new int[n];
A3 = new int[p];
cout<<"Enter "<<m<<" elements of A1 :";
for(int i=0;i<m;i++)
cin>>A1[i];
cout<<"Enter "<<n<<" elements of A2 :";
for(int i=0;i<n;i++)
cin>>A2[i];
cout<<"Enter "<<p<<" elements of A3 :";
for(int i=0;i<p;i++)
cin>>A3[i];
int gap = FindGap3Arrays(A1,m,A2,n,A3,p);
cout<<"The min gap of 3 A1, A2 and A3 is :"<<gap;
getchar();
return 0;
}
On Sat, Jun 18, 2011 at 2:55 PM, Dumanshu <duman...@gmail.com> wrote:
> @Ashish: In ur example you have found a min distance for a and c. Now
> to proceed because we have to find out min distance for two out of
> three arrays with the third array in between i.e. u need to find
> occurrence of a c b or a b c or b a c or ... in the merged array. Now
> quite possible these occurences might not be continuous so how are u
> going to proceed?
>
> Your order of m+n+p is fine for merging but to find the occurrence of
> a,b,c it would go like O((size of merged array)^3). so 3 for loops.
> for(i=0;i<sizeofmergedlist;i++) //for each element
> {
> now say a[i] belongs to array a
> for(j=i+1;j<sizeofmergedlist;j++)
> {
> keep goin until u find occurrence of some (other array other than a)
> lets say we have b now
> for(k=j+1;k<sizeofmergedlist;k++)
> keep going until u find some occurrence of c
> }
> now min_dist = max mod(a[i]-a[j],a[i]-a[k],a[k]-a[j]);
> }
>
> So for every element we are updating the min_dist. Is this what you
> are trying to do here? sorry i dont get your algo.
>
> Thanks
> Dumanshu
> On Jun 18, 12:06 am, Ashish Goel <ashg...@gmail.com> wrote:
> > say the arrays are
> >
> > a 6,7,9
> > b 3,4,5
> > c 1,2,8
> >
> > the merged array would be
> >
> > 1c
> > 2c
> > 3a
> > 4b
> > 5b
> > 6a
> > 7a
> > 8c
> > 9a
> >
> > 1c,2c cant be compared as they are from same array..next is 3a this
> implies
> > 3-2 =1 is min distance
> >
> > P.S: you can merge these in O(m+n+p) [merge from bottom as they are
> already
> > sorted]
> >
> > Best Regards
> > Ashish Goel
> > "Think positive and find fuel in failure"
> > +919985813081
> > +919966006652
> >
> >
> >
> > On Sat, Jun 18, 2011 at 12:24 AM, Dumanshu <duman...@gmail.com> wrote:
> > > @Ashish: could u plz explain ur algo in detail. "walk over the merged
> > > list to get adjacent min distance and different tags" this would be of
> > > the order O(m*n) say we merge A1 A2 of size m and n respectively.
> > > Also, now how do u go ahead with the 3rd array? didn't get ur
> > > solution.
> >
> > > Harshal's solution looks fine. ny bugs?
> >
> > > On Jun 17, 9:13 pm, Ashish Goel <ashg...@gmail.com> wrote:
> > > > merge two and if required third array keeping array tag with the
> > > elements
> > > > walk over the merged list and see adjacent distance which is minimum
> with
> > > > the condition that the tage of the adjacent elements are different
> >
> > > > Best Regards
> > > > Ashish Goel
> > > > "Think positive and find fuel in failure"
> > > > +919985813081
> > > > +919966006652
> >
> > > > On Fri, Jun 17, 2011 at 9:36 PM, Dumanshu <duman...@gmail.com>
> wrote:
> > > > > U have got 3 sorted arrays A1 A2 and A3 having m n and p elements
> > > > > respectively. A gap of 3 arrays is defined to be max distance
> between
> > > > > 3 nos if they are put on a no line say u pick three 2 12 and 7 then
> > > > > the gap is 10. Now u have to find an efficient way of chosing 3 nos
> > > > > from these 3 seperate arrays (A1, A2, A3) such that their gap is
> > > > > minimum. Of course if a num say 2 occurs in all 3 then gap is 0!!!
> >
> > > > > --
> > > > > You received this message because you are subscribed to the Google
> > > Groups
> > > > > "Algorithm Geeks" group.
> > > > > To post to this group, send email to algogeeks@googlegroups.com.
> > > > > To unsubscribe from this group, send email to
> > > > > algogeeks+unsubscr...@googlegroups.com.
> > > > > For more options, visit this group at
> > > > >http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text -
> >
> > > > - Show quoted text -
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com.
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
> >
> > - Show quoted text -
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
--Navneet
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
