may be to figure out the range while reading the numbers or taking the mos as input... we can have two variables (min and max) that contains the minimum and maximum elements encountered so far respectively... i.e. whenever we read a no n we compare it with min and max... if n<min then min =n or if n>max then max = n;
so the range would lie between min and max.. correct me if I am wrong.. On Mon, Jun 28, 2010 at 2:20 PM, nisha goyal <[email protected]>wrote: > @abhirup: range is required in counting sort.... how can you decide that?? > please elaborate.... > > On Mon, Jun 28, 2010 at 12:01 PM, Abhirup Ghosh <[email protected]>wrote: > >> We can sort the array in O(n) time using counting sort. And then take >> the difference of consecutive elements in O(n) time to get the minimum >> one. >> >> -Abhirup >> >> >> >> On Mon, Jun 28, 2010 at 10:36 AM, Jagadish M <[email protected]> >> wrote: >> > In the general case, we can reduce Element-Distinctness(ED) problem to >> > this problem. Since ED has a lower bound of Omega(n log n), we cannot >> > get an O(n) algorithm for this problem. >> > >> > http://en.wikipedia.org/wiki/Element_distinctness_problem >> > >> > >> > -Jagadish >> > http://www.cse.iitb.ac.in/~jagadish<http://www.cse.iitb.ac.in/%7Ejagadish> >> > >> > >> > >> > On Jun 27, 5:55 pm, sharad kumar <[email protected]> wrote: >> >> How to find the two numbers whose difference is minimum among the set >> of >> >> numbers >> > >> > -- >> > You received this message because you are subscribed to the Google >> Groups "Algorithm Geeks" group. >> > To post to this group, send email to [email protected]. >> > To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> > 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
