Member Avatar for 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.

Edited by alien2006.happy because: n/a
  • 4 Contributors
  • 6 Replies
  • 264 Views
  • 3 Days Discussion Span
  • Latest Post Latest Post by Rashakil Fol
Member Avatar for iamthwee

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.

Member Avatar for iamthwee

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.

Member Avatar for Rashakil Fol

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

Member Avatar for mrnutty

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

Member Avatar for 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 ?

Member Avatar for 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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.