944,117 Members | Top Members by Rank

Ad:
Oct 30th, 2009
0

An Algorithm Problem

Expand Post »
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.
Last edited by alien2006.happy; Oct 30th, 2009 at 3:55 am.
Reputation Points: 10
Solved Threads: 0
Newbie Poster
alien2006.happy is offline Offline
6 posts
since Aug 2008
Oct 30th, 2009
0
Re: An Algorithm Problem
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.
Featured Poster
Reputation Points: 1536
Solved Threads: 431
Posting Expert
iamthwee is offline Offline
5,865 posts
since Aug 2005
Oct 30th, 2009
0
Re: An Algorithm Problem
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.
Featured Poster
Reputation Points: 1536
Solved Threads: 431
Posting Expert
iamthwee is offline Offline
5,865 posts
since Aug 2005
Oct 31st, 2009
2
Re: An Algorithm Problem
Let's say I can do it with no variables.
Team Colleague
Reputation Points: 1135
Solved Threads: 172
Super Senior Demiposter
Rashakil Fol is offline Offline
2,479 posts
since Jun 2005
Nov 1st, 2009
0
Re: An Algorithm Problem
Hint, a odd number plus a odd number equals a even number.
Reputation Points: 840
Solved Threads: 594
Senior Poster
firstPerson is offline Offline
3,865 posts
since Dec 2008
Nov 2nd, 2009
0
Re: An Algorithm Problem
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 ?
Reputation Points: 10
Solved Threads: 0
Newbie Poster
alien2006.happy is offline Offline
6 posts
since Aug 2008
Nov 2nd, 2009
3
Re: An Algorithm Problem
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.
Team Colleague
Reputation Points: 1135
Solved Threads: 172
Super Senior Demiposter
Rashakil Fol is offline Offline
2,479 posts
since Jun 2005

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in Computer Science Forum Timeline: Round Robin Completion Time
Next Thread in Computer Science Forum Timeline: Computer Science Research





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC