what he wanted to say was that first digit would be m/n and second digit m%n Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com
On Tue, May 8, 2012 at 10:31 AM, atul anand <atul.87fri...@gmail.com> wrote: > @arpit : your formula for converting base 10 to base n is bit wrong , > right formula should be :- > > > let given base 10 no is m and we need to convert it in base n. > then base n converted no is ( (m/n) * 10) + (m%n) ie 34 base 10 in base 6 > is ((34/6)*10) + (34%6) ie 54 > > > 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. > -- 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.
