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.

▲

12 hours ago | parent | next [-]

[deleted]

▲

ethan_smith a day ago | parent | prev | next [-]

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.

▲

FabHK a day ago | parent | prev [-]

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

▲

Arnavion a day ago | parent [-]

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.

	▲	FabHK a day ago \| parent [-]
		Oh yes, you're right.