May be this helps
http://ds-gyan.blogspot.com/2009/12/two-numbers-with-minimum-difference.html
On Sep 28, 10:28 am, "coolfrog$" <dixit.coolfrog.div...@gmail.com>
wrote:
> @ sorurav
> yes , the basic logic is required so that the code can be understood in
> single Run..
> i also request the same to all dear friends.....
> Regards..
>
>
>
>
>
> On Tue, Sep 28, 2010 at 8:11 PM, sourav <souravs...@gmail.com> wrote:
> > Hi Friends
>
> > This is an interesting problem and request you all to give a brief
> > intro to your code before putting the code. Or you may just mention
> > the under lying concept in the code. This will be of great help and
> > others will find it more ready to improve by adding there approach.
>
> > Coming back to the problem an O(n) solution can exist by following the
> > approach of building a min heap (or max heap) from an array of
> > elements. A mean heap from an array of elements can be built by
> > starting from middle element (all elements from mid +1 to end are them
> > selves single element min heaps) (references available in Cormen or
> > other books).
>
> > During constructing the mean heap always track the min difference
> > between any two elements in the so far constructed heap. At any
> > instant if you are handling root 'a' which has left child l and right
> > child r and aiming to build a min heap rooted at a, then the following
> > cases arise
>
> > 1. a is less than both l and r. In this case no movement of a is
> > required. Now find |a-l| = x and |a-r| = y. 'a' cannot have a
> > difference z with any element under tree rooted at l such that z < x
> > becuase l is the least element in the tree rooted at l. Similarly 'a'
> > cannot have a difference z' with any element under tree rooted at r
> > such that z' < r. So least of x and y is the min diff between any
> > elements in the so far constructed min heap rooted at 'a'.
>
> > 2. a is less than l but greater than r. In this case r will replace a
> > and a need to be pushed down the its right child. While pushing 'a'
> > down keep calculating the differences between 'a' and 'r' as long as
> > 'a' is not pushed down to a node where it is the min element. While
> > you keep calculating also keep track of the min diff calculated so far
> > (say 'p'). Compare this 'p' with |a-l| and min diff between any two
> > elements for the tree rooted at l. Least of these three will be the
> > min diff between any 2 elements for the min head rooted at 'r' (which
> > replaced 'a''s position.
>
> > 3. Both 'l' and 'r' are less than 'a'. Take the lesser or 'l' and 'r'
> > and replace that with 'a' and push 'a' down as in case 2 (normal min
> > heap construction algo).
>
> > Thus we can continue building the min heap and at the end have the min
> > diff between any 2 elements in the array. Just we keep tracking the
> > min diff, we can also keep note of the 2 elements than are
> > contributing to this min diff my adding some more steps.
>
> > This idea is all based on the fact that min heap can be constructed
> > from an array in linear time.
>
> > Thanks,
> > Sourav
>
> > On Sep 27, 1:32 pm, rahul <rahulr...@gmail.com> wrote:
> > > If their is no constrain on assumptions.
>
> > > 1.Sort the array.
> > > 2. check the dif between 2 elements.
>
> > > { 99,35,45,33,88,9098,112,33455,678,3}
>
> > > sorted arrary : { } would be something.
> > > now update the min_diff.
>
> > > another example : { 7,8,1,3,5,4}
> > > sorted arrary : { 1,3,4,5,7,8}
> > > min diff is 1.
>
> > > Please correct me if i missed something.
>
> > > On Mon, Sep 27, 2010 at 1:13 PM, satish <satish....@gmail.com> wrote:
> > > > step1>construct heap using siftdown. // time complexity wil be O(n)
> > and
> > > > space complexity O(1).
> > > > step2>take mindifference=a[1].
> > > > step3>for i=1 ,i<=n/2 do
> > > > { find the difference of
> > (root,root-left),(root,root->right)and
> > > > (root->left,root->right).and maintain mindifference is the smallest
> > > > difference of among
> > > > three differences.
> > > > }
> > > > step4>return mindifference.
>
> > > > plz correct me if im wrong....
>
> > > > --
> > > > You received this message because you are subscribed to the Google
> > Groups
> > > > "Algorithm Geeks" group.
> > > > To post to this group, send email to algoge...@googlegroups.com.
> > > > To unsubscribe from this group, send email to
> > > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups
> > > > .com>
> > <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googleg
> > roups.com>
>
> > > > .
> > > > For more options, visit this group at
> > > >http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups
> > .com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> *Divesh*
> (¨`·.·´¨) Always
> `·.¸(¨`·.·´¨ ) Keep
> (¨`·.·´¨)¸.·´Smiling!
> `·.¸.·´" Life can give u 100's of reason 2cry,but u can give life 1000's
> of reasons 2Smile"
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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.
