0

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.

Edited by alien2006.happy: n/a

4
Contributors
6
Replies
7
Views
8 Years
Discussion Span
Last Post by Rashakil Fol
0

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.

0

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.

0

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 ?

0

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.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.