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
I think if range is till n2, max passes for radix sort will be 3.
by subtracting 1 to all the numbers we get the max range to n2-1 and radix
sort can be done in 2 passes.
but what will happen when if we have a '0' in array and then we subtract 1
to it?
On Tue, May 8, 2012 at 9:48 AM, atul anand
Read the problem for constraints
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Tue, May 8, 2012 at 11:12 AM, Mahesh Thakur tmahesh...@gmail.com wrote:
I think if range is till n2, max passes for radix sort will be 3.
by subtracting 1 to all the
@arpit : why algo subtracts 1 from each number of the input?
On Sun, May 6, 2012 at 12:02 AM, Arpit Gupta arpitgupta.211...@gmail.comwrote:
1) Substract 1 from each no.
2) Now after substracting 1 from each no, convert it to base n.
for example for n=6,the number 36 will be converted to 55.
@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
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
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
@jeevitesh yeah that may be right but it requires extra space as lot
of space will be wasted...
On May 5, 1:44 pm, Jeevitesh jeeviteshshekha...@gmail.com wrote:
Hi all,
I am new to this group.
My last post was deleted i do not know the reason behind it.
I will explain my logic here:-
as
Hi Shiva.
You are right we will be wasting a lot of memory.
But still it depends like if we have lot of numbers in the range of 1, n^2
present in the input array then this trade off is not bad.
The issue here is we cannot otherwise sort it in O(n) time unless and until
we have extra space.
So we
I think I couldn't make myself clear...
This line in your algorithm *After this just iterate through the aux array
printing the index aux[i] times.*
this makes your algorithm O(n^2) since the size of aux is n^2 and in the
worst case the complete traversal of aux may be required.
Saurabh Singh
1) Substract 1 from each no.
2) Now after substracting 1 from each no, convert it to base n.
for example for n=6,the number 36 will be converted to 55. (36-1=35 and
35 when converted to base 6 is 55)
3) Thus all the nos in the range 1 to 6^2 can be mapped to numbers between
00 to 55.
4) Now
^ This is what I was talking about in my earlier post.But the problem is
how\ to convert the base of each number in O(1) time ( and then reconvert
to base 10 in O(n)) .I may be missing some trick here.Still working on it.
Saurabh Singh
B.Tech (Computer Science)
MNNIT
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
^ 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) =
You can use Radix Sort.
It will have a Time Complexity of O(n).
On Saturday, May 5, 2012 12:17:15 AM UTC+5:30, Algobiz 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
15 matches
Mail list logo
