hi guys
i am new 2 this group.i hav one solution to find duplicate num.
lp=rp=(n/2)+1 //lp-left ptr and rp-right ptr
lh=rh=result=0 //lh-left half and rh-right half
result^=num(lp) //^--xor
for(;(lp>-1||rp<n);lp--,rp++)
{
if(lp>-1){
if(num(lp)^result==lh || num(lp)^result==rh)
return num(lp)
}
if(rp<n){
if(num(rp)^result==lh || num(rp)^result==rh)
return num(rp)
}
lh=result^num(lp) //lets say lp >-1 v can also do this update in if loop but need one more variable
rh=result^num(rp) //lets say rp<n
result=lh^rh^num(n/2 + 1)
}
guys i didnt check out 4 negative numbers.
On 12/21/05, Vijay Venkat Raghavan N <[EMAIL PROTECTED]> wrote:
Hi,
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é
