An Algorithm Problem

[alien2006.happy]

Let say we have N number and N is odd. Among the N numbers, two of them equal to each other except one. For example, let's say we have 7 numbers, which could be 5, 3, 4, 1, 3, 5, 1. Only 4 is distinct, other number always has anther one member equal to it. Then how can we design a algorithm to find the distinct number(among N numbers) in linear time with only one variable introduced.

Let's say I have a homework question. Let's say I have no intention of actually doing it myself.

Let's say I post that question on an internet forum and see how many people will try and post the answer.

Let's say I have a homework question. Let's say I have no intention of actually doing it myself.

Let's say I post that question on an internet forum and see how many people will try and post the answer.

[Rashakil Fol]

Let's say I can do it with no variables.

[mrnutty]

Hint, a odd number plus a odd number equals a even number.

[alien2006.happy]

Yeah, thank you for your hint. I guess I could solve it now. Let me make it public. We could just using XOR with all this numbers, and after that, we could get the number that we want.
But just let me change that problem a little. If there are 2N+2 numbers, and only 2 numbers are distinct. Other number always has another member, which is equal to it. Then how can we solve it using the least memory and the least time now ?

[Rashakil Fol]

At the very minimum, if this is an array of N-bit integers, we'll need 2N bits of state, because there's no way to represent two arbitrary N-bit integers with fewer than that amount of information. So if there's a very clever solution, it'll have two accumulatory variables. Maybe there isn't -- maybe it needs something like three or four variables, because of the nature of the problem. Of course, it might need O(N) space and O(N) time if you can't do better than a hash table.