Yes thanx for that...Gene had already mentioned that in somewhat different way.And now I feel like a floppy disk for not being able to think the obvious. Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com
On Sun, May 6, 2012 at 10:20 PM, Arpit Gupta <arpitgupta.211...@gmail.com>wrote: > O(1) base conversion can here be done as follows:-(works only when numbers > are in range 0 to n^2-1) > *From base 10 to base n > *let given base 10 no is m and we need to convert it in base n. > then base n converted no is (m/n)(m%n) ie 34 base 10 in base 6 is > (34/6)(34%6) ie 54 > > Now i think you can yourself write base n to base 10 conversion. > > > On Sun, May 6, 2012 at 11:13 AM, saurabh singh <saurab...@gmail.com>wrote: > >> ^ And this completes the solution.... >> >> Saurabh Singh >> B.Tech (Computer Science) >> MNNIT >> blog:geekinessthecoolway.blogspot.com >> >> >> >> On Sun, May 6, 2012 at 11:12 AM, Gene <gene.ress...@gmail.com> wrote: >> >>> Ah, but you can pick the radix to be n. Then at most 3 passes will >>> always sort the array. O(3n) = O(n), so you are done. >>> >>> This topic has come up before. There is code at >>> http://groups.google.com/group/algogeeks/msg/90ce2df194aba2d2 . >>> >>> It is true this code assumes math including mod takes constant time, >>> but that's normal for RAM computation models used for most algorithms. >>> >>> Gene >>> >>> On May 5, 4:32 am, saurabh singh <saurab...@gmail.com> wrote: >>> > After giving some thought,I think even radix sort may not be >>> sufficient. >>> > Complexity of radix sort is O(k*n) where k is the number of buckets >>> > required to sort the given range. >>> > The number of buckets is proportional to the number of bits required to >>> > represent the *maximum number in the given range.*For our case the >>> maximum >>> > number is O(n^2).Hence *the number of buckets required would be >>> > proportional to log(n^2) in the worst case.* >>> > Hence the worst case complexity for the given constraints using radix >>> sort >>> > would be *O(n*(log n^2)) = O(n*logn).* >>> > This is no better than comparision sort.A slight optimization that we >>> can >>> > make is to use a higher base which would reduce the number of buckets >>> > required but would add the cost of converting each number into the >>> higher >>> > base. >>> > Somehow I am getting convinced worst case O(n) algorithm may not be >>> > possible.Working on the mathematical proof. >>> > Saurabh Singh >>> > B.Tech (Computer Science) >>> > MNNIT >>> > blog:geekinessthecoolway.blogspot.com >>> > >>> > On Sat, May 5, 2012 at 8:37 AM, saurabh singh <saurab...@gmail.com> >>> wrote: >>> > > @cegprakash They are n numbers lying in the range 1 to n^2.Not >>> necessarily >>> > > sorted. >>> > > eg 3 4 1 2 5 8 (6 numbers satisfying the conditions given in the >>> problem) >>> > > Saurabh Singh >>> > > B.Tech (Computer Science) >>> > > MNNIT >>> > > blog:geekinessthecoolway.blogspot.com >>> > >>> > > On Sat, May 5, 2012 at 5:17 AM, Prakash D <cegprak...@gmail.com> >>> wrote: >>> > >>> > >> The range 1 to n^2 is already sorted >>> > >>> > >> On Sat, May 5, 2012 at 12:17 AM, Algobiz < >>> deepak.arulkan...@gmail.com> >>> > >> wrote: >>> > >> > How to sort n numbers in the range of 1 to n^2 in O(n).. Any >>> ideas? >>> > >>> > >> > -- >>> > >> > 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/-/PGgMdaIbGIsJ. >>> > >> > 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. >>> >>> >> -- >> 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. >> > > > > -- > Arpit Gupta > B.Tech Third Year > Computer Science And Engineering > M.N.N.I.T Allahabad > arpitgupta.211...@gmail.com > > -- > 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.
