A better solution?
I was looking at a question:
Q. Given n numbers of which all numbers are repeated (at least once) other than one. We have to find that number.
Numbers range is to 10^9, thus using count sort would do no good.!
Adding the numbers one by one to a dictionary was another option (and a good one as the complexity is O(n)). But this has high implementation requirements.!
Can someone suggest some better answer to this problem.? :-/
techie1991
Junior Poster in Training
72 posts since Feb 2010
Reputation Points: 36
Solved Threads: 9
O(n) solution:
int value;
for(int i = 0; i < myArray.Length; i++) {
value ^= myArray[i];
}
Console.WriteLine("{0} occurs only once", value);
Works when all other numbers come in pairs. Make sure I get a good grade.
Momerath
Nearly a Senior Poster
3,384 posts since Aug 2010
Reputation Points: 1,232
Solved Threads: 558
pyTony
pyMod
5,358 posts since Apr 2010
Reputation Points: 782
Solved Threads: 852
very good answer momerath..
I must really start using these boolean operators.. :)
techie1991
Junior Poster in Training
72 posts since Feb 2010
Reputation Points: 36
Solved Threads: 9
