First of all to adak. This problem cannot use your logic as even if the range is from 1 to 65000, as you have given for example, i can easily pick put 4 numbers like 1,10,456,65000. The Complexity of your algo is 65000, mine wud be 4lg4 = 8.
Pramod: Great point man, even I thought it had to be nlgn, but well, I am not sure now.
-Vijay
On 12/8/05, Dhyanesh <[EMAIL PROTECTED]> wrote:
Hashing has collisions. What if all the numbers hash to the same position (in the worst case)? Then you will be back to square one. Hashing is just a hack for any problem ... not a proper solution.
-Dhyanesh
On 12/8/05, mathmoi <[EMAIL PROTECTED] > wrote:
Dhyanesh wrote:
> I agree it is faster but you cannot use it will all inputs. I gave you a
> test case and you still havent come out on how to solve that. Your algorithm
> is limited to a range of numbers only. It will be very slow even for numbers
> like 2^31 or so which fit into the size of an integer (and you can run it
> only if you have 2GB virtual memory). Give it such inputs and you will it
> will perform much much worse than doing the nlgn algorithm. One more thing
> how are you going to handle -ve numbers.
>
> Tell me how fast it is with this set ... { - 2^30, -23, 64,1 ,4,1 , 2^31 }
> ... try make it run faster than nlogn sorting.
What if he use a hash table instead of an array? The hash table only
need to be a little bit bigger than to original array and could use
very big (or even negative) index.
Mathieu Pagé
