@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.
