Re: [algogeeks] Give Algo to do this in O(n)
Counting Sort is really a Bad option for this Problem as range is not given yes range can be find in single traversal but think if largest element is 10^9 and size of the array is just about 10^3 Counting Sort = O(10^9) Simple Sorting = O(10^4) Counting sort will perform bad in this case both in terms of Space Requirements and Time On Mon, Oct 10, 2011 at 11:25 PM, snehi jain wrote: > ankur : i wont say its the best way, but it can be used >in one traversal the range can be determined and then count sort > can be applied. > > > > On Mon, Oct 10, 2011 at 10:56 PM, Ankur Garg wrote: > >> @Sravan ..Counting Sort takes O(n) time but it needs range of nos to be >> known >> @Snehi jain..there is no range given so am not sure if count sort will >> work ,Can you please elaborate a bit on ur method >> >> Ankur >> >> >> On Mon, Oct 10, 2011 at 10:09 PM, sravanreddy001 < >> sravanreddy...@gmail.com> wrote: >> >>> Just went throught what a count sort is at >>> http://en.wikipedia.org/wiki/Counting_sort >>> >>> If all the elements are distinct which is possible, will this count sort >>> have any use? >>> >>> Also, the sorting takes O(nlogn) time right? >>> >>> Did I miss anything? >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To view this discussion on the web visit >>> https://groups.google.com/d/msg/algogeeks/-/08bcRsmFYJgJ. >>> >>> 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. >> > > -- > 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. > -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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.
Re: [algogeeks] Give Algo to do this in O(n)
ankur : i wont say its the best way, but it can be used in one traversal the range can be determined and then count sort can be applied. On Mon, Oct 10, 2011 at 10:56 PM, Ankur Garg wrote: > @Sravan ..Counting Sort takes O(n) time but it needs range of nos to be > known > @Snehi jain..there is no range given so am not sure if count sort will work > ,Can you please elaborate a bit on ur method > > Ankur > > > On Mon, Oct 10, 2011 at 10:09 PM, sravanreddy001 > wrote: > >> Just went throught what a count sort is at >> http://en.wikipedia.org/wiki/Counting_sort >> >> If all the elements are distinct which is possible, will this count sort >> have any use? >> >> Also, the sorting takes O(nlogn) time right? >> >> Did I miss anything? >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To view this discussion on the web visit >> https://groups.google.com/d/msg/algogeeks/-/08bcRsmFYJgJ. >> >> 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. > -- 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.
Re: [algogeeks] Give Algo to do this in O(n)
@Sravan ..Counting Sort takes O(n) time but it needs range of nos to be known @Snehi jain..there is no range given so am not sure if count sort will work ,Can you please elaborate a bit on ur method Ankur On Mon, Oct 10, 2011 at 10:09 PM, sravanreddy001 wrote: > Just went throught what a count sort is at > http://en.wikipedia.org/wiki/Counting_sort > > If all the elements are distinct which is possible, will this count sort > have any use? > > Also, the sorting takes O(nlogn) time right? > > Did I miss anything? > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/08bcRsmFYJgJ. > > 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.
Re: [algogeeks] Give Algo to do this in O(n)
Just went throught what a count sort is at http://en.wikipedia.org/wiki/Counting_sort If all the elements are distinct which is possible, will this count sort have any use? Also, the sorting takes O(nlogn) time right? Did I miss anything? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/08bcRsmFYJgJ. 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.
Re: [algogeeks] Give Algo to do this in O(n)
@ ankur: if space is not the consideration first sort them using count sort and then look for the pair with the min. difference .. i think it should work . Snehi On Mon, Oct 10, 2011 at 7:21 PM, anubhav gupta wrote: > @deoki try for 1001,999,998,1 > > > On Mon, Oct 10, 2011 at 6:57 PM, Deoki Nandan wrote: > >> just find minimum and secon minimum by taking two variables in O(n) >> >> On 10 October 2011 17:57, sandeep nagamalli wrote: >> >>> @Shiva: How can min heap be uesd, can you eloborate a bit. >>> >>> As far as i see, the best possible is O(nlogn) i.e by sorting and >>> scanning over the complete array once. >>> >>> >>> >>> >>> On Mon, Oct 10, 2011 at 9:49 AM, shiva@Algo wrote: >>> I think Min heap will do that.. On Mon, Oct 10, 2011 at 12:37 AM, Ankur Garg wrote: > Given an unsorted array of Integers > > Find 2 nos whose diff is minimum > > Say Array is 4 2 18 19 11 8 5 > > Nos are 18 and 19 > > Algo shud be of O(n) > > -- > 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. >>> >>> >>> >>> -- >>> Thanks&Regards: >>> -sandeep >>> >>> >>> -- >>> 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. >>> >> >> >> >> -- >> **With Regards >> Deoki Nandan Vishwakarma >> IIT ROORKEE >> 9760340784 >> for Computer Science Interview Material see my home page >> https://sites.google.com/site/deokinandanmaterials/ >> >> * >> * >> >> -- >> 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. > -- 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.
Re: [algogeeks] Give Algo to do this in O(n)
@deoki try for 1001,999,998,1 On Mon, Oct 10, 2011 at 6:57 PM, Deoki Nandan wrote: > just find minimum and secon minimum by taking two variables in O(n) > > On 10 October 2011 17:57, sandeep nagamalli wrote: > >> @Shiva: How can min heap be uesd, can you eloborate a bit. >> >> As far as i see, the best possible is O(nlogn) i.e by sorting and scanning >> over the complete array once. >> >> >> >> >> On Mon, Oct 10, 2011 at 9:49 AM, shiva@Algo wrote: >> >>> I think Min heap will do that.. >>> >>> >>> On Mon, Oct 10, 2011 at 12:37 AM, Ankur Garg wrote: >>> Given an unsorted array of Integers Find 2 nos whose diff is minimum Say Array is 4 2 18 19 11 8 5 Nos are 18 and 19 Algo shud be of O(n) -- 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. >>> >> >> >> >> -- >> Thanks&Regards: >> -sandeep >> >> >> -- >> 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. >> > > > > -- > **With Regards > Deoki Nandan Vishwakarma > IIT ROORKEE > 9760340784 > for Computer Science Interview Material see my home page > https://sites.google.com/site/deokinandanmaterials/ > > * > * > > -- > 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.
Re: [algogeeks] Give Algo to do this in O(n)
just find minimum and secon minimum by taking two variables in O(n) On 10 October 2011 17:57, sandeep nagamalli wrote: > @Shiva: How can min heap be uesd, can you eloborate a bit. > > As far as i see, the best possible is O(nlogn) i.e by sorting and scanning > over the complete array once. > > > > > On Mon, Oct 10, 2011 at 9:49 AM, shiva@Algo wrote: > >> I think Min heap will do that.. >> >> >> On Mon, Oct 10, 2011 at 12:37 AM, Ankur Garg wrote: >> >>> Given an unsorted array of Integers >>> >>> Find 2 nos whose diff is minimum >>> >>> Say Array is 4 2 18 19 11 8 5 >>> >>> Nos are 18 and 19 >>> >>> Algo shud be of O(n) >>> >>> -- >>> 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. >> > > > > -- > Thanks&Regards: > -sandeep > > > -- > 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. > -- **With Regards Deoki Nandan Vishwakarma IIT ROORKEE 9760340784 for Computer Science Interview Material see my home page https://sites.google.com/site/deokinandanmaterials/ * * -- 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.
Re: [algogeeks] Give Algo to do this in O(n)
@Shiva: How can min heap be uesd, can you eloborate a bit. As far as i see, the best possible is O(nlogn) i.e by sorting and scanning over the complete array once. On Mon, Oct 10, 2011 at 9:49 AM, shiva@Algo wrote: > I think Min heap will do that.. > > > On Mon, Oct 10, 2011 at 12:37 AM, Ankur Garg wrote: > >> Given an unsorted array of Integers >> >> Find 2 nos whose diff is minimum >> >> Say Array is 4 2 18 19 11 8 5 >> >> Nos are 18 and 19 >> >> Algo shud be of O(n) >> >> -- >> 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. > -- Thanks&Regards: -sandeep -- 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.
Re: [algogeeks] Give Algo to do this in O(n)
I think Min heap will do that.. On Mon, Oct 10, 2011 at 12:37 AM, Ankur Garg wrote: > Given an unsorted array of Integers > > Find 2 nos whose diff is minimum > > Say Array is 4 2 18 19 11 8 5 > > Nos are 18 and 19 > > Algo shud be of O(n) > > -- > 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.
[algogeeks] Give Algo to do this in O(n)
Given an unsorted array of Integers Find 2 nos whose diff is minimum Say Array is 4 2 18 19 11 8 5 Nos are 18 and 19 Algo shud be of O(n) -- 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.
