Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

It's funny how the author fails to apply the XOR trick in the two missing values problem:

> We can thus search for u by applying this idea to one of the partitions and finding the missing element, and then find v by applying it to the other partition.

Since you already have u^v, you need only search for u, which immediately gives you v.



Indeed - once you have u^v, finding u in one partition immediately gives you v = (u^v)^u, eliminating the need for the second search.


How can you find u? That's what the author explains next.


The article says to use the "XOR of all elements" method to find u^v, then do the partitioning, then use the "XOR of all elements" method on the first partition to find u, then use the "XOR of all elements" method on the second partition to find v.

tromp is saying the last step can be simplified. There is no need to use the "XOR of all elements" method on the second partition to find v, since the earlier steps have given us u^v and u, so simply XORing those two values together gives v.


Oh yes, you're right.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: