i feel, it can be done in O(n), find the median of the array, remove the median from the array, again find the median of the array(put back the first median to the array). difference of these two element will be min. Thank you, Siddharam
On Tue, Aug 16, 2011 at 10:40 AM, Dave <dave_and_da...@juno.com> wrote: > @Shuaib: You could sort the numbers in O(n) with a radix sort, and > then finding the min is easy. Mind you, the radix sort might be slower > than an O(n log n) sort, but still it satisfies the O(n) constraint. > > Dave > > On Aug 15, 8:41 pm, Shuaib <aries.shu...@gmail.com> wrote: >> That won't work. And I don't think an O(n) solution is possible. >> >> -- >> Shuaibhttp://twitter.com/ShuaibKhanhttp://www.bytehood.com/ >> >> On 16-Aug-2011, at 6:25 AM, sukran dhawan <sukrandha...@gmail.com> wrote: >> >> >> >> > find the minimum of two numbers in a loop o(n) and subtract the two >> >> > On Tue, Aug 16, 2011 at 6:13 AM, Brijesh Upadhyay >> > <brijeshupadhyay...@gmail.com> wrote: >> > Algorithm to find the two numbers whose difference is minimum among the >> > set of numbers. For example the sequence is 5, 13, 7, 0, 10, 20, 1, 15, 4, >> > 19 The algorithm should return min diff = 20-19 = 1. Constraint - Time >> > Complexity O(N) >> >> > -- >> > You received this message because you are subscribed to the Google Groups >> > "Algorithm Geeks" group. >> > To view this discussion on the web >> > visithttps://groups.google.com/d/msg/algogeeks/-/U8gTWUISJn8J. >> > 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 >> > athttp://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 algogeeks@googlegroups.com. >> > To unsubscribe from this group, send email to >> > algogeeks+unsubscr...@googlegroups.com. >> > For more options, visit this group >> > athttp://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 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. > > -- 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.
